Lowest Common Ancestor

Problem Statment

Given a root of the binary tree and nodes n1 and n2. Find the lowest common ancestor of the nodes.

Example:
The lowest common ancestor for D and E in the above tree is C. The least common ancestor for D and B is A.

Lowest common ancestor with parent pointer
This problem is easily solved if parent pointer is given. All you need is to count distance to the root for both the nodes. If the distance for node n1 is l1 and node n2 is l2, find the larger of l1 and l2 and move the corresponding node up the tree by that distance. Once that is done, then we just need to move both the nodes up the tree one step at a time and check if the parent node is same. If it is then we have the common ancestor.

Here is the code:

Node *lca_parent(Node *n1, Node *n2) {

        Node *t1 = n1, *t2 = n2;

        int c1 = 0, c2 =0;

        // Find the distance to the root for n1
        while(t1 != NULL) {
            t1 = t1->parent;
            c1++;
        }

        // Find the distance to the root for n2
        while(t2 != NULL) {
            t2 = t2->parent;
            c2++;
        }

        // Move up the tree for the node that is
        // furthest from the tree
        if (c1 < c2) {
            while(c1 < c2) {
                n2 = n2->parent;
                c1++;
            }
        } else {
            while (c2 parent;
                c2++;
            }
        }

        // Keep pn moving up the tree  for both nodes
        // n1 and n2 until we have the same parent.
        while (n1 != n2) {
            n1 = n1->parent;
            n2 = n2->parent;
        }

        return n1;
}

Lowest common ancestor without parent pointer
If parent pointer is not given we can find lowest common ancestor by searching the nodes in the tree. We can use post order traversal and keep track if we have seen the node in the current subtree. Once we have seen the node in both subtrees or the current node is one of the node and the other node has been found in one of this node's subtree then we are done. The code is given below:

/*
 * Find lowest common ancestor
 * @param root - root of the tree
 * @param n1 - one of the node whose ancestor is to be determined 
 * @param n2 - the other node whose ancestor is to be determined
 * @param result - the lowest common ancestor
 */
bool lca(Node* root, Node *n1, Node *n2, Node **result) {

    if (root == NULL)
        return false;

    bool l = lca(root->left, n1, n2, result);
    bool r = lca(root->right, n1, n2, result);

    bool res = true;
    if (l && r) {
        *result = root;
    } else if((root == n1 || root == n2) && (l || r)) {
        *result = root;
    } else if (root != n1 && root != n2) {
        res = false;
    }
    
    return res || l || r;
}