Challenge – First Common Ancestor

Question: How would you find the first common ancestor of two nodes in a binary search tree? First as in the lowest in the tree. Another way to ask is to find the lowest common ancestor of two nodes.

Challenge: Do you know the answer to this question? Post in the comments. Answers will be posted March 6th.

Meanwhile, check out the challenges from previous weeks here.

Answer:

TreeNode findFirstCommonAncestor(TreeNode root, TreeNode p,
	TreeNode q) {

    if (root == null) {
        return null;
    }

    if (root == p || root == q) {
	return root;
    }

    TreeNode left = findFirstCommonAncestor(root.left, p, q);
    TreeNode right = findFirstCommonAncestor(root.right, p, q);

    if ((left == p && right == q) ||
        (left == q && right == q)) {
	return root;
    }

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

Alternate:

TreeNode findFirstCommonAncestor(TreeNode root, int p, int q) {

    if (root == null) {
        return null;
    }

    if (root.value == p || root.value == q) {
	return root;
    }

    if (root.value > p && root.value > q ) {
        return findFirstCommonAncestor(root.left, p, q);
    } 
    else if (root.value < p && root.value < q ) {
        return findFirstCommonAncestor(root.right, p, q);
    } 
    else {
        return root;
    }
}

Thanks Dave and Sunil for pointing out the alternate solution.
 

19 Responses

  1. I have not read the paper yet (thank you Cosmin for posting it), but the posts here are all incomplete. Here are the points to consider and test your proposed algorithm on:
    1. Your routine should return null if one or both nodes you are looking for are not in the tree. All posted algorithms fail this test if one of the two values are present and the other is missing.
    2. Your routine should work if one of the sought nodes is the ancestor of the other. Again, both proposed solutions in the text fail this, since the moment you find one of the sought nodes the algorithm returns and the children of that node are never examined.
    3. Your routine should work if the two sought values are the same.

  2. AW says:

    Okay. How to do this problem in an iterative way? One possibility is that the BST is totally unbalanced.

    NODE *LCA(NODE *t, int sml, int lgr){
    if(t == NULL) return NULL;
    if(sml > lgr) {printf(“sml=%d larger than lgr=%d\n”, sml, lgr); exit(1);}
    while(t && !(t->data > sml && t->data data > lgr) t = t->left;
    if(t->data right;
    }
    return t;
    }

  3. AW says:

    Sorry! did not see that the solution was posted already:(

  4. AW says:

    It is a binary search tree. So given two nodes say x and y. Assume x x and < y.

    The algorithm: Starting from root, if it is greater than both x and y, then we check the left child of the root. If the root is less than both x and y, then we check the right child of the root. This check will keep going until find a node z (x<z<y).

  5. dave says:

    Why is the official answer an algorithm that runs in time linear in the size of the tree when there are algorithms that use the fact that the tree is a binary search tree to find the answer in time linear in the depth of the tree?

  6. Sunil Verma says:

    Just do in-order traversal of the binary tree, the FIRST node whose value lies between the values of two given nodes is the lowest common ancestor.

  7. Amit says:

    Recursive solution?

    Node p1 = leftNode;
    Node p2 = rightNode;

    Node ancestor(p1,p2){
    if(p1==p2) return p1; // common ancestor
    if(p1.parent != root) return ancestor(p1.parent, p2);

    if(p2.parent != root) return ancestor(p1, p2.parent);

    }

  8. jl says:

    Following up on my previous post: it’s the smallest/largest (depending on the ordering) element found in /ps/ and /qs/.

  9. jl says:

    If the type doesn’t provide any insight in how it’s represented, but provides method for doing common traversals (pre- and postorder in particular), you can:

    do a preorder traversal and store the nodes before any of the two sought nodes are found, call them /ps/.

    Then do a postorder traversal and skip all elements while not both sought nodes are seen, call the rest /qs/.

    Now the LCA is the element present both in /ps/ and in /qs/.

    Maybe this solution is discussed in the paper above, I’m not sure. It’d be nice if someone could confirm or show that the above algorithm works.

  10. Ahnfelt says:

    It swallowed half my code, so here’s a repost

    A O(1) space, O(log(n)) time algorithm (if the tree is balanced).


    data Tree a = Node a (Tree a) (Tree a) | Leaf

    visit n x1 x2 = if x1 < x2
    then visit' n x2 x1
    else visit' n x1 x2

    visit' Leaf _ _ = None
    visit' (Node v l r) x1 x2 | v >= x1 && v <= x2 = Some (Node v l r)
    visit' (Node v l r) x1 x2 | v < x1 = visit' r x1 x2
    visit' (Node v l r) x1 x2 | v > x2 = visit' l x1 x2
    visit' _ _ _ = None

  11. Ahnfelt says:

    A O(1) space, O(log(n)) time algorithm (if the tree is balanced).


    data Tree a = Node a (Tree a) (Tree a) | Leaf

    visit n x1 x2 = if x1 = x1 && v <= x2 = Some (Node v l r)
    visit' (Node v l r) x1 x2 | v x2 = visit' l x1 x2
    visit' _ _ _ = None

  12. Dima says:

    Do a binary search for node 1 and keep track of every node that you see along the way. Then do the same for node 2. Compare your results and take the smallest node that is found in both sets.

  13. bigmell says:

    DFS from the first root and mark all the nodes as seen. DFS from the second root and take the node at the lowest depth that has a seen value O(n).

  14. DougR says:

    Given:
    root = tree root
    n1 = node1
    n2 = node2

    //make sure n1 is smaller than n2
    if (n1>n2) swap(n1,n2);
    //find point where n1<root<n2
    while(root!=null){
    if (n2left;
    else if(n1>root) root = root->right;
    else return root;
    }

  15. witek says:

    Two pass algorithm with O(1) memory and O(log n) time.

    pass 1) start from node n1 and n2, for each go up to the root, to know how deep in tree we are, record height as h1, and h2.
    pass 2) restart from n1 and n2. for deeper node (say n2, with h2 depth), perform h2-h1 jumps to the parent. Then start synchronously travering up by one in n1 and n2, and stop when you land in some step you have same node on both sides (which will be eventually root).

  16. Find the parents of both nodes ordered in their natural order of parenthood. Take the intersection of both sets and pick the smallest element in the intersection.

  17. Cosmin says:

    The paper “The LCA problem revisted” solves the your task in O(n) preprocessing time and O(1) time for each query.

    http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.2223&rep=rep1&type=pdf

  18. dave says:

    Repost of code:

    search(node* n1, node* n2, node* root) {
    int minValue = min(n1->value, n2->value);
    int maxValue = max(n1->value, n2->value);
    while (true) {
     //check if min and max reside on different sides of root
     if (minValue <= value && maxValue >= root->value) return root;

     if (minValue < left)
      //both smaller, go left
      root = root->left;
     else
      //both larger, go right
      root = root->right;
     }
    }

  19. dave says:

    The first common ancestor is the same as the root of the smallest tree containing both nodes.

    Start at the root, search for the two nodes. Stop when the two nodes would reside in different subtrees.


    search(node* n1, node* n2, node* root) {
    int minValue = min(n1->value, n2->value);
    int maxValue = max(n1->value, n2->value);
    while (true) {
    //check if min and max reside on different sides of root
    if (minValue value && maxValue >= root->value) return root;

    if (minValue left;
    else
    //both larger, go right
    root = root->right;
    }
    }

Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

XHTML: These are some of the tags you can use: <a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>