How can I find the common ancestor of two nodes in a binary tree?

Answer 1

Tarjan's off-line least common ancestors algorithm is good enough (cf. also Wikipedia). There is more on the problem (the lowest common ancestor problem) on Wikipedia.

Answer 2

Well, this kind of depends how your Binary Tree is structured. Presumably you have some way of finding the desired leaf node given the root of the tree - simply apply that to both values until the branches you choose diverge.

If you don't have a way to find the desired leaf given the root, then your only solution - both in normal operation and to find the last common node - is a brute-force search of the tree.

Answer 3

Nick Johnson is correct. But keep in mind that if your nodes have parent pointers, a slight variation on his algorithm is possible. For both nodes in question construct a list containing the path from root to the node by starting at the node, and front inserting the parent.

So for 8 in your example, you get (showing steps): {4}, {2, 4}, {1, 2, 4}

Do the same for your other node in question, resulting in (steps not shown): {1, 2}

Now compare the two lists you made looking for the first element where the list differ, or the last element of one of the lists, whichever comes first.

This algorithm requires O(h) where h is the height of the tree. If the tree is balanced, that is O(log(n)).

---

Regardless of how the tree is constructed, if this will be an operation you perform many times on the tree without changing it in between, there are other algorithms you can use that require O(n) [linear] time preparation, but then finding any pair takes only O(1) [constant] time. For references to these algorithms, see the the lowest common ancestor problem page on Wikipedia. (Credit to Jason for originally posting this link)

Answer 4

I have made an attempt with illustrative pictures and working code in Java,

http://www.technicalypto.com/2010/02/least-common-ancestor-without-using.html

Answer 5

This can be found at:- http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html

tree_node_type *LowestCommonAncestor( tree_node_type *root , tree_node_type *p , tree_node_type *q) { tree_node_type *l , *r , *temp; if(root==NULL) { return NULL; }

if(root->left==p || root->left==q || root->right ==p || root->right ==q)
{
    return root;
}
else
{
    l=LowestCommonAncestor(root->left , p , q);
    r=LowestCommonAncestor(root->right , p, q);

    if(l!=NULL && r!=NULL)
    {
        return root;
    }
    else
    {
        temp = (l!=NULL)?l:r;
        return temp;
    }
}

}