CareerCup

I am assuming you are looking for the *least* common ancestor.

2. binary search tree

public static BSTNode lca(BSTNode root, BSTNode n1, BSTNode n2) {
    if(root == null || n1 == null || n2 == null) return null;
    if(n1 == root) return n1;
    if(n2 == root) return n2;
    if(n1.value < root.value && n2.value < root.value) {
        return lca(root.left, n1, n2);
    } else if (n1.value > root.value && n2.value > root.value) {
        return lca(root.right, n1, n2);
    }
    return root;
}

for the bst the time comp[lexity required is just the O(H) where H is the height of the bst :)

//to search for common ancestor in a binary tree, the code would be

treeNodePtr findLCA(treeNodePtr root, int p, int q) {

// no root no LCA.
if(!root) {
return NULL;
}

// if either p or q is the root then root is LCA.
if(root==p || root==q) {
return root;
} else {
// get LCA of p and q in left subtree.
treeNodePtr l=findLCA(root->left , p , q);

// get LCA of p and q in right subtree.
treeNodePtr r=findLCA(root->right , p, q);

// if one of p or q is in leftsubtree and other is in right
// then root it the LCA.
if(l && r) {
return root;
}
// else if l is not null, l is LCA.
else if(l) {
return l;
} else {
return r;
}
}
}

This is a fairly common question that is asked in many interviews. Refer to the Lowest Common Ancestor tutorial on TopCoder.

I found the last method(using the Euler Tour method to traverse the graph) more easier to understand than the other methods mentioned in the tutorial.

Do a pre order traversal of tree. Scan the list of nodes obtained by pre order traversal. In this list a node which is last such node which was visited before these 2 nodes should be common ancestor.

This should work for for binary tree and binary search tree.

I think this question was posted to this site just recently (< 5 days ago)

For a BST this is very easy and Vijay has given the right algorithm.
For a binary tree you can calculate the list of nodes from the root to a particular node.
Do this for both the nodes. Compare their list of ancestors. The last element of the longest matching prefix is the LCA. Very simple.
(nobrainer .co .cc)