Binary Search Tree : Lowest Common Ancestor

  • + 2 comments

    Took a second, but I get it. It only actually uses one of the loops. It also doesn't need to care how v1 and v2 are ordered.

    No need to obfuscate it, though.

    node * lca(node * root, int v1,int v2)
    {
        node *cur{root};
        while (cur->data > v1 && cur->data > v2) cur = cur->left;
        while (cur->data > v1 && cur->data > v2) cur = cur->right;
        return cur;    
    }
    
    • + 1 comment

      A bit confusing for this and I found a counter example.

      I had a tree: 8 4 9 1 6 2 5 7 3

      lca of 2 and 3 should be 2, but this logic return 1

      • + 2 comments
                    8
                 /    \
                4       9
              /   \
            1       6
           / \
          3   2
        

        This is your tree. The answer code runs fine.

        • + 1 comment

          Hi, shouldn't the tree be like this:

                 8
               /    \
              4       9
            /   \
           1       6
            \
             2
              \
               3
          
          • + 0 comments

            No, for a tree: 8 4 9 1 6 2 5 7 3. It should look like this: (forgiven me about my bad indentation)

                        8
                     /    \
                   4       9
                /     \
              1          6
               \       /  \
                2     5    7
                 \
                  3
            
        • + 0 comments

          Tree flase

    • + 0 comments

      what if current->data>v1&&current->data