We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Data Structures
  3. Trees
  4. Binary Search Tree : Lowest Common Ancestor
  5. Discussions

Binary Search Tree : Lowest Common Ancestor

  • Thrashans + 3 comments

    Thanks, that was really helpful. This is my C++ Solution

    node * lca(node * root, int v1,int v2)
{
    node *cur{root};
    for (; cur->data > v1 && cur->data > v2; cur = cur->left);
    for (; cur->data > v1 && cur->data > v2; cur = cur->right);
    return cur;    
}
    • codeharrier + 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;    
}
      • dongxy90 + 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

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

          This is your tree. The answer code runs fine.

          • shail289 + 1 comment

            Hi, shouldn't the tree be like this:

                   8
     /    \
    4       9
  /   \
 1       6
  \
   2
    \
     3
            • maximshen + 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
          • hongocvuong1998 + 0 comments

            Tree flase

      • coolrahuliit1501 + 0 comments

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

    • m_orazow + 1 comment

      This is wrong for the following input:

      6
7 5 12 9 8 10
8 10
      • kartheek_kappag1 + 0 comments

        also wrong for below output 7 4 2 7 1 3 6 8 6 8

    • Mikeiyan + 0 comments

      the second loop should be checking if the cur is less than v1 and v2 because if we had 8 , 11, 10, 12, 9, 13 and v1 = 9, v2 =13 your loops would return 8 which is wrong.