Find the lowest common ancestor of two given nodes

Problem:

Given a binary tree, find the lowest common ancestor of two given nodes. All the nodes in the tree will be unique.

The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).

Algorithm:

1. If the current node is null, return null
2. If the current node is either p or q return the current node, because it could be an ancestor. So return the current node. Use an array foundNodes to keep track if both nodes to be searched are found.
3. Recursively traverse both the left and right subtrees, storing the results from both subtrees. Continue this traversal until the foundNodes array has a length of 2 (indicating both nodes have been found).
4. If both left and right are not null, then the current node is LCA. (Because p and q are found in both sides.)
5. If only one subtree return a node, then propogate it upwward.

The algorithm works on the principle that if nodes p and q are in different subtrees, the current node is their Lowest Common Ancestor (LCA). If both p and q are in the same subtree, the ancestor must be located in the same subtree.

Solution & Visualize:

The animation/visualization below demonstrates how the algorithm works.

// The idea is when a node is found matching p or q,
// then stop propogating downward
function findLCA(root, p, q, foundNodes) {
    if (root === null) return null;

    // Current node is p or q,
    // then current node could be an ancestor
    if ([p, q].includes(root.data)) {
        foundNodes.push(root);
        return root;
    }

    let left = null;
    let right = null;
    if (foundNodes.length < 2) {
        left = findLCA(root.left, p, q, foundNodes);
    }

    if (foundNodes.length < 2) {
        right = findLCA(root.right, p, q, foundNodes);
    }

    // If both subtrees are not null,
    // then the current node is the LCA
    if (left !== null && right !== null) {
        return root;
    }

    return left !== null ? left : right;
}

const nodes = [1,2,3,4,5,6,7,8,9,null,null,null,13];
const root = buildTree(nodes, 0, nodes.length);

findLCA(root, 9, 13, []); // 1
findLCA(root, 7, 13, []); // 3
                                        

class TreeNode {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function buildTree(nodes, index, size) {
    if (index < size) {
        if (nodes[index] === null) {
            return null;
        }

        let root = new TreeNode(nodes[index]);
        root.left = buildTree(nodes, 2 * index + 1, size);
        root.right = buildTree(nodes, 2 * index + 2, size);

        return root;
    }

    return null;
}