Binary Search Tree : Lowest Common Ancestor

  • + 68 comments

    Solution is based on the following thought: The value of a common ancestor has to always be between the two values in question.

    static Node lca(Node root,int v1,int v2)
    {
        //Decide if you have to call rekursively
        //Samller than both
        if(root.data < v1 && root.data < v2){
            return lca(root.right,v1,v2);
        }
        //Bigger than both
        if(root.data > v1 && root.data > v2){
            return lca(root.left,v1,v2);
        }
    
        //Else solution already found
        return root;
    }
    
    • + 1 comment
      [deleted]
      • + 1 comment
        [deleted]
        • + 1 comment

          here is problem solution in java python c++ and c programming.

          HackerRank Binary Search Tree : Lowest Commone Ancestor solution

          • + 0 comments

            First thing! The tree shown is diagram is wrong BST. How is 4 on the left of 3?

    • + 6 comments

      this was my approach but it is failing testcase 2 and i don't know why. checking my 'output' for 5 hackos it reads 'CORRECT' so i don't know what's going on

      • + 3 comments

        That the output reads CORRECT does just mean that this is the output you should get, its a bit weird. If you could post your code I will look through it to see if I see something wrong :)

        • + 0 comments

          thanks for your help :)

          i took another look and caught the bug, same as in above code

          consider what ultimately gets returned by every function...

        • + 1 comment

          i have returned A , but output is incorrect for testcase 2 my code node * lca(node * root, int v1,int v2) { static node *safe; if((root -> data >= v1 && root -> data <= v2) || (root -> data <= v1 && root -> data >= v2)) safe = root; return safe; if(root -> data < v1) lca(root -> right , v1 , v2); else lca(root -> left , v1 , v2); return safe; }

          • + 4 comments

            your logic is incorrect after.....

            if(root -> data < v1)

            lca(root -> right , v1 , v2);

            else

            lca(root -> left , v1 , v2);

            return safe; } In this case you are not checking v2. you may lose the trail of v2 while traversing. In your decision logic your root depends on v1 as well as v2...... go for the simple code...

            node * lca(node * root, int v1,int v2)

            {

            if(v1<root->data && v2<root->data)
                root=lca(root->left,v1,v2);
            else if(v1>root->data && v2>root->data)
                root=lca(root->right,v1,v2);
            return root;
            

            }

            • + 1 comment

              Awesome, can you please explain why assigning it to root will work correctly but fails if used as node* only for test case 2?

              Thanks in advance!!

              • + 2 comments

                root->(right)->x->(right)->v1->(right)->v2

                Consider this. LCA is v1's address.But since you're returning only the address without storing it in some value,it is getting lost.When control gets to x it will return it's own root ie x because each parametrised "root" is local.However storing it in root updates the value of the local root with the LCA and as the chain of hierarchy goes upwards the LCA keeps getting returned.

                • + 0 comments

                  great answer...

                • + 1 comment

                  Hello, Can someone explain below scenario I have added below input in custom testcase for current program. 6 4 2 3 1 7 6 0 5 v1 =0 and v2 = 5 which are not present in my tree still it shows common parent as 4. and testcase shows pass.

                  • + 0 comments

                    Kindly follow the constraints while creating a custom testcase :)

            • + 1 comment

              Please explain why assigning it as root works but when used as Node root ,iit fails the test case 2.

            • + 0 comments

              thanks man!!

            • + 0 comments

              if(Math.min(v1,v2)<=root.data && Math.max(v1,v2)>=root.data) { return root;} if(v1>root.data){ return lca(root.right, v1, v2); } if(v1

        • + 0 comments

          Could you please explain it step by step.

      • + 0 comments

        node * lca(node * root, int v1,int v2) { if(root==NULL) { return NULL; }

        if(v1>root->data && v2>root->data)
            {
            lca(root->right,v1,v2);
        }
        

        else if(v1data && v2data) { lca(root->left,v1,v2); }

        return root; } same here test case 2 is where my code fails but in case of try and run it's working pretty well.

      • + 0 comments

        BTW, you can always add print statements temporarily for debugging your own code.

      • + 1 comment

        The details are really perfect. The details give me a proper idea about the lowest common ancestor Hostsailor. The problem page is giving the proper explanation with the help of an appropriate representation of a binary tree. That is perfect for a better understanding of a person.

        • + 0 comments

          Moderators please ban this user.

      • + 0 comments

        Try simple approach:

        Node *lca(Node root, int v1,int v2) { // Write your code here. Node roottemp = root; Node* arrV1[50] = {0}; Node* arrV2[50] = {0}; int index1 = 0; int index2= 0; int min =0;

            if(root == NULL)
            {
                return NULL;
            }
        
            while(root!= NULL)
            {
                if(root->data == v1)
                {
        
                    arrV1[index1] = root;
                    index1++;
                    break;
                }
                arrV1[index1] = root; 
                root->data > v1? (root = root->left) : (root = root->right);
                index1++;
            }
        
            root = roottemp;
        
            while(root!= NULL)
            {
                if(root->data == v2)
                {
                    arrV2[index2] = root;
                    index2++;
                    break;
                }
                arrV2[index2] = root; 
                root->data > v2? (root = root->left) : (root = root->right);
                index2++;
            }
        
            index1>index2? min = index2: min = index1;
        
            for (int i=0 ; i<min; )
            {
                   if(arrV1[i] == arrV2[i])
                   {
                       roottemp = arrV1[i];
                       i++;
                   }
                   else{
                       break;
                   }
            }return roottemp;
        }
        

        }; //End of Solution

    • + 1 comment

      This will not pass the case where v1 is an ancestor of v2.

      • + 2 comments

        It works correctly: if v1 is an ancestor of v2, then the algorithm will traverse the tree until root is the node containing v1. At this point root.data < v1 is not true and root.data > v1 is not true, therefore both of the if-statements are bypassed and root is returned, which is the correct behavior.

        • + 0 comments

          can u help me to bug what is wrong with testcase 2 for my code.

        • + 1 comment

          If v1 is the ancestor of v2, then should the LCA = parent of v1 instead of v1?

          • + 3 comments

            No, if v1 is an ancestor of v2, v1 will be the lca. (this confused me for quite some time and I hope they change the challenge description to account for this.)

            • + 0 comments

              Agreed, it confused me too until I read your comment! Thanks :)

            • + 0 comments

              How can v1 be the ancestor of itself? I am still confused.

              Or, are you referring to the correct answer that the question will accept?

            • + 0 comments

              Thanks!

    • + 0 comments

      Perfect solution! (y) :-)

    • + 2 comments

      couldn't think of a more perfect solution than this one.

      • + 0 comments

        That is because, its the same as the code in Editorial Section

      • + 11 comments

        I prefer an iterative solution to this problem rather than recursive. The code is similarly brief, and there isn't any need to load up the call stack.

        static Node lca(Node root,int v1,int v2)
        {
            Node temp = root; // not necessary, just use root, just a leftover from a different attempt.
            
            while (true) {
                if (temp.data > v1 && temp.data > v2) {
                    temp = temp.left;
                } else if (temp.data < v1 && temp.data < v2) {
                    temp = temp.right;
                } else {
                    return temp;
                }
            }
        }
        
        • + 0 comments

          I agree. Especially considering that this is clearly tail-recursive (which makes it trivial to convert to an iterative solution).

        • + 0 comments

          I came with exact this solution!

        • + 0 comments

          awesome solution:)

        • + 0 comments

          This code gives the output as 1 and result is correct. In an another code output is 4 and then too result is correct.

        • + 0 comments

          Elegant and simplistic solution. wow.

        • + 0 comments

          I vastly prefer this version! Simplicity and elegance.

        • + 0 comments

          Instead of while(true) shouldn't we use while(temp)? Better to have Null checks ahead.

        • + 0 comments

          this solution is so good but this works with Binary Search Tree but if is a Normal Binary Tree not ordered we should use the recursive because is better than iterative

        • + 0 comments

          Neat code. I think this is in case of an ordered tree where lt < root < rt. If this was not the case, I think using Queue to push the children; level by level would solve it.

        • + 0 comments

          thanks dude

        • + 0 comments

          it's a perfect solution!!

    • + 2 comments

      I did it the same way, with a minor performance improvement: I arrange v1 and v2 so that I know which is larger:

      node* lca_(node* root, int a, int b)
      {
          if (b < root->data) {
              return lca_(root->left, a, b);
          }
          else if (a > root->data) {
              return lca_(root->right, a, b);
          }
          return root;
      }
      
      node* lca(node* root, int a, int b)
      {
          if (a < b) {
              return lca_(root, a, b);
          }
          return lca_(root, b, a);
      }
      
      • + 2 comments

        it's not really an improvement, lca is done with the assumption v1 < v2; which would be done before calling lca: as is with all test cases for this problem.

        • + 1 comment

          Two things:
          The first: The problem never tells us in the constraints that v1 < v2, that's an assumption that happens to be true this time.

          If you did make that assumption, why this code:

          if(root.data < v1 && root.data < v2){
              return lca(root.right,v1,v2);
          }
          //Bigger than both
          if(root.data > v1 && root.data > v2){
              return lca(root.left,v1,v2);
          }
          

          If you are assuming v1 < v2, then if root.data < v1, root.data cannot possibly >= v2.

          My code uses this tautology do its advantage by only checking what is necessary to determine what we need to know. Therefore, it is better than your code, because it uses x/2 + 1 comparisons, where x is the number of comparisons you make, and I maintain that you should check beforehand, because the check itself can only have a marginal cost but since the whole algorithm relies on it, you shouldn't simply trust that whoever uses your code is going to follow your rules.

          • + 0 comments

            i made throw(exception) assumption is wrong swapping everything in the beginning simplifies problem significantly

        • + 0 comments

          not here certainly because i was getting WA in some test cases assuming v1

      • + 0 comments

        I think this is much cleaner apporach by arranging v1 < v2

        It is much easier to understand the logic.

        performance is also slightly better.

        you don't need else.. just two if commands and a return

        if (...) return left_tree_lca

        if (...) return right_tree_lca

        return root

        Great jobs!! :)

    • + 0 comments

      man, at first sight I thought this would be more like a medium question... but after thinking it through... meh

    • + 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;    
      }
      
      • + 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

      • + 1 comment

        This is wrong for the following input:

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

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

      • + 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.

    • + 2 comments

      for example, for a tree: 4 2 3 1 7 6 8

      if you want to find the lowest common ancestor of 6 and 8, your code outputs 7, but the correct answer should be 4!

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

        This will be the tree, don't know what you did.

      • + 0 comments

        Correct answer should be 7, as tree has been presented by @latishk

    • + 2 comments

      I like simplicity of your solution. My brain finally has started to figure out (picking up) a pattern in recursion. But the only problem that I am facing as of now is I overcomplicated solution. Such as the one below.

      if((root->data < v2 && root->data > v1)||(root->data > v2&&     root->data < v1)){
          return root;
      }else if(root->data > v1&&root->data > v2){
          return lca(root->left,v1,v2);
      }else if(root->data < v1&&root->data < v2){
          return lca(root->right,v1,v2);
      }else{
          return root;
      }
      
      • + 1 comment

        this solution is pretty convincing. The only issue i am seeing is that in your first if either of v1 or v2 is at the root node then your condition is not responding to that moves to the sec elseif where as it should return root in first place..... lets say v1=2, v2=5 and in the tree root is 2 and root.right is 5 then your if condition is failing...hope this will help..

        • + 1 comment

          Thanks.

          That's what I was looking at right now when I was solving the problem from Cracking the Coding Interview. Also, if I use the simple code snippet given at the top, my cases are failing. It is not returning me with the immidiate common ancester. It is rather returning the very top node.

          Please comment on this issue, is it just me? Or we have a problem in the code above?

          Yep I guess I need to add one more if condition namely if v1 or v2 is equal to root->data, return root.

          Thanks.

          • + 1 comment

            you have given the end 'return root' in else condition where as it should be returned in every condition. just remove last else...

            • + 0 comments

              Yep my code works fine. Root is returned only in the condition when above if's are not matching. I am taking about the code at very top of the page. For me it's not giving proper results. Like it gives the last common ancestor rater then immidiate one.

      • + 0 comments

        why do we traverse left when both v1 and v2 are greater than root? Should we not traverse left?

        I am rusty with the concepts

    • + 1 comment

      I think that in the first part of the code (// smaller than both) is useless because if both v1 and v2 are greater than root.data so the LCA is the root itself because all nodes on the right of the root are greater than it so the conditions inside the function will be only :-

      //Bigger than both
      if(root.data > v1 && root.data > v2){
          return lca(root.left,v1,v2);
      }
      //Else solution already found
      return root;
      

      I submited this code and it passed all test cases ...

      • + 0 comments

        Hey, I've never actually used return in front of the recursive function call itself. Can you explain, what will the "return lca(root.left,v1,v2)" do exactly ?

    • + 0 comments

      This also works.

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

      My approach is very similar but I am getting error in TestCase 2.I have been trying to figure that out for an hour but couldn't.What's so special about case 2?

      • + 1 comment

        same situation here, bro :/

        • + 0 comments

          test case 2 has been screwy for 2 years far as i can tell. i've configured my code to return 1 and 4 and neither passes. the example given at the top of the description also doesn't fit BST criteria I don't think?

    • + 0 comments

      consider this case: Tree size 3 and its contents are 4,2,1 and search for 2 and 1. As per correct solution provided, the output is returning as 2 but it should be 4 right?

    • + 1 comment

      this solution doesnot work with case 2 because you have not made a condition on root that if it is not null then check that v1 and v2 are greater or less.

      • + 0 comments

        i couldnt understand what u r trying to say about checking whether v1 and v2 are greater or less? what difference does that make because in the penultimate step v1(2) becomes temp and then we check whether temp1->data>v2 || temp1-data

    • + 0 comments

      What about some edge cases? 1) What if v1 == v2? 2) What if v1 is an ancestor for v2? Would your solution work then?

    • + 0 comments

      Hmm I never thought to use a value test. I used a recursive inTree() function to test if a value was in a particular subtree. The running times of all test cases was 0 so the recursion didn't hurt in this case.

      https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/submissions/code/25912799

      bool inTree(node *head, int value) {
          if (head == NULL) {
              return false;
          } else if (value == head->data) {
              return true;
          } else {
              return inTree(head->left, value) || inTree(head->right, value);
          }
      }
      
      node * lca(node * root, int v1,int v2)
      {
          if (inTree(root->left, v1) && inTree(root->left, v2)) {
              return lca(root->left, v1, v2);
          } else if (inTree(root->right, v1) && inTree(root->right, v2)) {
              return lca(root->right, v1, v2);
          } else {
              return root;
          }
      }
      
    • + 0 comments

      pls help! i can't trace the code especially when it states (4<1 &&4 <7) or (4>1&&4>7). how the recursive calls r taking place..

    • + 1 comment

      pls help! i can't trace the code especially when it states (4<1 &&4 <7) or (4>1&&4>7). how the recursive calls r taking place..

      • + 0 comments

        That particular piece of logic would return false since the test 4<1 returns false and the test 4>7 returns false.

    • + 1 comment

      My solution was so convoluted.

      vector pathTo(node* root,int key){
        vector path;
        node* current = root;
      
        while (current != NULL && current->data != key) {
          path.push_back(current);
          if      (key data) current = current->left;
          else if (key > current->data) current = current->right;
      
        }
        if (current)
          path.push_back(current);
        return path;
      }
      
      node*lca(node*root,int x,int y){
        vector pathX = pathTo(root, x),
                      pathY = pathTo(root, y);
      
        unordered_set s;
        int i;
        for (i = pathX.size()-1; i >= 0; --i)
          s.insert(pathX[i]);
        for (i = pathY.size()-1; i >= 0; --i) {
          if (!s.insert(pathY[i]).second) break;
        }
        return pathY[i];
      }
      • + 0 comments

        Thank u!!

    • + 5 comments

      I think in this counter example it wouldnt work:

      v1 is 1 and v2 is 7

          4       
        /   \
      2       6
       \     /  \
        3   5    7    
           /
          1
      

      Answer we would get is 4 and the correct answer is 6.

      • + 0 comments

        I saw no such BST because BST strictly follows elements(root.left)

      • + 0 comments

        This does not adhere to the constructor for the BST. For example, as soon as 1 is entered into the tree, the constructor would go down the left path until it got to node(2).left and place it there. It would never go down the right path since 1 is lower than the root.

      • + 0 comments

        1 cannot go to the right of 4 as it will break the BST invariant

    • + 0 comments

      Nice job. You can alternatively try to solve it iteratively like this to achieve O(1) space complexity since recursion takes O(log n) space.

      HackerRank solutions.

    • + 0 comments

      It is better to first check if you have already found the lce and then decide which path to go.

      To, the same idea without brackets would be like this:

      node * lca(node * root, int v1,int v2)
      {
         int diff1 = root->data - v1, diff2 = root->data - v2;
         if (diff1 * diff2 <= 0) return root;
         if (diff1 < 0) return lca(root->right, v1, v2);
         return lca(root->left, v1, v2);
      }
      
    • + 0 comments

      I don't think it is a correct solution.. It will always return the root of tree after final evaluation.. All test cases except test case 2 are working becuase fro all of them root of the tree is the LCA..

      Node lca(Node root,int v1,int v2){
          return root;     
       }
      

      Try this, you will know what I am trying to say.. If you run the above code it will also fail only test case 2..

      After we get the required node, in the shrinking phase of recursions we need a way so that we can contain the deepest recursive node in root and not the actual root of tree.. though I am not sure how to do that..

    • + 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;
      }
      
    • + 0 comments

      this doesn't work for all the test cases.

    • + 0 comments

      Can someone explain this recursive solution to me? I'm not able to get the correct return value.

    • + 0 comments

      Beautiful!

    • + 0 comments

      The example input given to the problem in the description has Node 5 on left of Root node 1.

      Which I do think will fail your solution.

    • + 0 comments
      static Node lca(Node root,int v1,int v2)
          {
              Node curr = root;
              
              while ((curr.data < v1 && curr.data < v2) || (curr.data > v1 && curr.data > v2)) {
                  if(curr.data < v1 && curr.data < v2){
                      curr = curr.right;
                  }
                  else {
                      curr = curr.left;
                  }
              }
              
              return curr;
          }
      

      Changed it to iterative so the space complexity is O(1)

    • + 0 comments

      why do you have return lca(root.right, v1,v2) as opposed to lca(root.right,v1,v2)?

    • + 0 comments

      BUT! The first example is not following your presumption (3 is not between 4 and 5). If it's just a mistake then it's confusing.

    • + 0 comments

      Brilliant solution!

    • + 0 comments

      I don't think this is going to work because consider a tree with 3 as the root node and has 4 as a left child and 5 as a left child. 5 has a right child 6. The least common ancestor for 4 and 6 would be 3, but according to your logic, it would be 5, which is incorrect. Value of common ancestor need not be between the two values. Look at the first example case of the problem

    • + 0 comments

      You should also have written, that you're doing a binary search for both values.

    • + 0 comments

      has to consider the scenario when v1 or v2 equal to root.data

    • + 0 comments

      here another java solution, but this solution destroys the tree lol

      	public static Node lca(Node root, int v1, int v2) {
              if(root==null) {
               return null; 
              }
              if(root.data==v1||root.data==v2) {
               return  root; 
              }
              if(root.left==null&&root.right==null) {
                if(root.data==v1||root.data==v2) {
                    return root; 
                }
                    return null;  
              }
             root.left = lca(root.left,v1,v2);
             root.right =  lca(root.right,v1,v2); 
              if(root.left==null||root.right==null) {
                  if(root.left!=null) {
                    return root.left; 
                  }
                   return root.right; 
              }
      
              return root; 
          }
      
    • + 0 comments

      Why are you smarter than me?

    • + 1 comment

      C++ solution :

      Node *lca(Node *root, int v1,int v2) {
      		// Write your code here.
              while((v1>root->data && v2>root->data) || (v1<root->data && v2<root->data))
              {
                  if (v1>root->data) root=root->right;
                  else root=root->left;
              }
              return root;
          }
      
      • + 1 comment
        Node *add1 [25];
             Node *add2[25];
                int i=0,j=0;
            Node *lca(Node *root, int v1,int v2) {
        		// Write your code here.
               
                if(v1>root->data) {
                    root=lca(root->right,v1,v2);
                    add1[i++]=root;
                    
                }
                 else if(v2>root->data) {
                    root=lca(root->right,v1,v2);
                    add2[j++]=root;
                    
                }   
                else if(v1<root->data) {
                    root=lca(root->left,v1,v2);
                    add1[i++]=root;
                    
                }
                 else if(v2<root->data) {
                    root=lca(root->left,v1,v2);
                    add2[j++]=root;
                    
                }   
                Node *a;
                for(int i=0;i<25;i++){
                    for(int j=0;j<25;j++){
                        if(add1[i]==add2[2]) {a= add1[i]; return a;}
                    }
                }
        
                
            }
        

        why this not working

        • + 0 comments
          1. i was basically storing the address of the of each node through which we are passing for v1 and v2 in add1 and add2 respectively
          2. i want to ask few questions:-
          3. solution is a structure (in this question) , when we are calling Lca function (MYTREE.LCA(ROOT,V1,V2) , does the "instance of struct solution " will have --> add1[25] , add2[25], int i,j ; when function is called
          4. on each function call (root=lca(root->left,v1,v2) ) in each "IF" statement does the add1[25] , add2[25], int i,j , will again take memory OR one single copy of add1[25] , add2[25], int i,j ; is only there, as only one insance is made;
    • + 1 comment

      Easiest solution https://www.youtube.com/watch?v=N9yepbXdOkI

      • + 1 comment

        Node *add1 [25]; Node *add2[25]; int i=0,j=0; Node *lca(Node *root, int v1,int v2) { // Write your code here.

            if(v1>root->data) {
                root=lca(root->right,v1,v2);
                add1[i++]=root;
        
            }
             else if(v2>root->data) {
                root=lca(root->right,v1,v2);
                add2[j++]=root;
        
            }   
            else if(v1<root->data) {
                root=lca(root->left,v1,v2);
                add1[i++]=root;
        
            }
             else if(v2<root->data) {
                root=lca(root->left,v1,v2);
                add2[j++]=root;
        
            }   
            Node *a;
            for(int i=0;i<25;i++){
                for(int j=0;j<25;j++){
                    if(add1[i]==add2[2]) {a= add1[i]; return a;}
                }
            }
        
        
        }
        
        • + 0 comments
          i was basically storing the address of the of each node through which we are passing for v1 and v2 in add1 and add2 respectively
          i want to ask few questions:-
          solution is a structure (in this question) , when we are calling Lca function (MYTREE.LCA(ROOT,V1,V2) , does the "instance of struct solution " will have --> add1[25] , add2[25], int i,j ; when function is called
          on each function call (root=lca(root->left,v1,v2) ) in each "IF" statement does the add1[25] , add2[25], int i,j , will again take memory OR one single copy of add1[25] , add2[25], int i,j ; is only there, as only one insance is made;
          
    • + 0 comments

      Straight to the point. Cool, thanks for sharing this thought.

    • + 0 comments

      never had experience with tree, so maybe a stupid question: how do you get "The value of a common ancestor has to always be between the two values in question."? at least the first picture shows that "3" is the common ancestor of "4" and "5".

    • + 0 comments

      Good post but I was wondering if you could write a litte more on this subject? I’d be very thankful if you could elaborate a little bit further. Appreciate it..! https://www.pikdo.online/

    • + 2 comments

      O(height) python solution:

      def lca(root, v1, v2):
          while(root != None):
              if(v1 > root.info and v2 > root.info):
                  root = root.right
              elif(v1 < root.info and v2 < root.info):
                  root = root.left
              else:
                  break
          return root
      
      • + 0 comments

        hey man , how can you think like that its amazing

      • + 0 comments

        Cleaned up a little:

        while root:
            if v1<root.info and v2<root.info:
                root=root.left
            elif v1>root.info and v2>root.info:
                root=root.right
            else:
                return root
        
    • + 0 comments

      This solution is false and will barely pass any test due to runtime errors and wrong answers. I don't know why it has this many upvotes while beeing crappy

    • + 0 comments

      I thought so too at fisrt, but this would not suit the first example they provide, where the lca of 4 and 6 is 3.

    • + 0 comments

      Had a similar thing with C but I'm getting seg faults. Any ideas? It works for half the test cases;

      struct node *lca(struct node *root, int v1, int v2) {
          if(root != NULL && root->data < v1 && root->data < v2){
              return lca(root->left, v1, v2);
          }
          if(root != NULL && root->data > v1 && root->data > v2){
              return lca(root->right, v1, v2);
          }
          else return root;
      }
      
    • + 1 comment
      [deleted]
      • + 0 comments

        Node *lca(Node *root, int v1,int v2) {

            if(v1>root->data && v2>root->data)
            root = lca(root->right,v1,v2);
            if(v1<root->data && v2<root->data)
            root = lca(root->left,v1,v2);
            return root;
        
        }
        
    • + 0 comments

      yes is exactly what I tought, the structure of the tree is already tell us how to proceed

    • + 0 comments

      that's very brilliant.

      but i tried tracing the path from root to key1 and taken this path into a queue. did the same for key2 and returned the last common integer among the two queues.

      complex right?

    • + 0 comments

      Thank you very, very much, RubenzZzZ!

    • + 0 comments

      My iterative approach

      public static Node lca(Node root, int v1, int v2) {
              if (root == null)
                  return null;
              Set<Node> set = new HashSet<>();
              set.add(root);
              Node node = root;
              while (node.data != v1) {
                  node = v1 < node.data ? node.left : node.right;
                  set.add(node);
              }
              set.add(node);
              Node n = root;
              node = root;
              while (set.contains(node)) {
                  n = node;
                  node = v2 < node.data ? node.left : node.right;
              }
              return n;
          }
      
    • + 0 comments

      just amazing

    • + 0 comments

      dang, didnt think of it! thank you so much!

    • + 0 comments

      good it helped me alot

    • + 0 comments

      I did the samething but getting a runtime error anytime there v1 or v2 eaqual root.info. Can anyone tell why? Posting my code above

    • + 0 comments

      I did the same thing but am running into errors then v1 or v2 are eaqual to node.info. Dont understand why

    • + 0 comments

      My Amazon interview experience https://freezefrancis.medium.com/amazon-sde-interview-experience-on-campus-e8444ee791b

    • + 0 comments

      Variant of this came in my interview: https://freezefrancis.medium.com/agoda-interview-experience-de6abc2c7347

    • + 0 comments

      This code does not pass all test cases

    • + 0 comments

      The solution is well thought, but I believe the following (custom) test case provides incorrect answer-

      6

      2 1 3 4 5 6

      3 4

      Expected - 1 Recieved - 3

      The tree is same as the first example. Kindly let me know if I am misunderstanding something.

    • + 0 comments

      Respect!