235. Lowest Common Ancestor of a Binary Search Tree

Loading...LeetCode

2nd try

time: O(n)

space: O(h), worst O(n)

var lowestCommonAncestor = function(root, p, q) {
    if (root === null) return root;

    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    
    return root;
};

1st try

time: O(n)

Space: O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
    if (containsB(p, q)) return p;
    if (containsB(q, p)) return q;

    const ids = [];
    ids[root.val] = root;

    const queue = [[root, root]];

    while (queue.length > 0) {
        const [node, parentNode] = queue.shift();
        if (node === null) continue;

        ids[node.val] = parentNode;
        queue.push([node.left, node]);
        queue.push([node.right, node]);
    }

    let current = p;
    const pPath = [p];
    while (ids[current.val] !== current) {
        pPath.unshift(ids[current.val]);
        current = ids[current.val];
    }

    current = q;
    const qPath = [q];
    while (ids[current.val] !== current) {
        qPath.unshift(ids[current.val]);
        current = ids[current.val];
    }

    let idx = 1;
    while (pPath[idx] === qPath[idx]) {
        idx++;
    }

    return pPath[idx - 1];
}

function containsB(node, b) {
    if (node === null) return false;

    if (node === b) {
        return true;
    }

    const left = containsB(node.left, b);
    const right = containsB(node.right, b);

    return left || right;
}