Binary Search Tree : Lowest Common Ancestor

  • + 0 comments

    I think there's a bug in your code. Your code doesn't address the condition when v1 or v2 = root, in that case, the lca is the parent of the current root but your code will return current root and that's why it may be failing some test cases. Let's say, for this bst,

        40
       /
      20    <-- v1
     /                  lca = 40
    10      <-- v2
    

    if we are given v1 = 20, v2 = 10 then if we go through your code it'll return 20 as the lca but actually 40 will be the lca.

    Have a look at my code. It passes all the test cases.

    node * lca(node * root, int v1,int v2)
    {
        if(v1<root->data && v2<root->data)
            if(node *tmp = lca(root->left, v1, v2))
                return tmp;
        if(v1>root->data && v2>root->data)
            if(node *tmp = lca(root->right, v1, v2))
                return tmp;
        return root;
    }