# Binary Search Tree : Lowest Common Ancestor

# Binary Search Tree : Lowest Common Ancestor

RubenzZzZ + 36 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; }`

jitendra_k + 0 comments [deleted]jitendra_k + 0 comments [deleted]rmccune + 4 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

RubenzZzZ + 2 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 :)

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

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

mohitaggarwal516 + 2 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;`

}

Sandeep_1991 + 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!!

saikat777 + 1 comment 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.

sandeshh1 + 0 comments great answer...

amala9 + 0 comments [deleted]stark007_sc + 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.

b0kater + 0 comments BTW, you can always add print statements temporarily for debugging your own code.

BlinkinBharg + 1 comment This will not pass the case where v1 is an ancestor of v2.

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

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

vidhi0007 + 1 comment If v1 is the ancestor of v2, then should the LCA = parent of v1 instead of v1?

StefanK + 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.)

nanthiran_2005 + 0 comments Agreed, it confused me too until I read your comment! Thanks :)

kapildevneupane1 + 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?

kar_santanu43 + 0 comments Thanks!

divyaaarthi + 0 comments [deleted]kiner_shah + 0 comments Perfect solution! (y) :-)

maverick55 + 2 comments couldn't think of a more perfect solution than this one.

RaviShekhar93 + 0 comments That is because, its the same as the code in Editorial Section

b0kater + 4 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; } } }

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

Mohit_Yadav_389 + 0 comments I came with exact this solution!

jaskaransingh_17 + 0 comments awesome solution:)

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

jonmcclung + 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); }`

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

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

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

aru_674 + 0 comments not here certainly because i was getting WA in some test cases assuming v1

ejan16 + 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!! :)

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

Thrashans + 2 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.

hongocvuong1998 + 0 comments Tree flase

coolrahuliit1501 + 0 comments what if current->data>v1&¤t->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

Moghaak + 1 comment 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; }`

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

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

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

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

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

Shivan111 + 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 ?

peterkirby + 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; }`

KeyTapper + 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?

arjunthedragon + 1 comment same situation here, bro :/

RJB3_MechLearn + 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?

manoharkotapati + 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?

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

akay1997 + 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

mantas + 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?

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

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

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

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

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

dgodfrey + 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]; }`

tanya20_1995 + 0 comments Thank u!!

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

alexmiragall + 0 comments [deleted]taieddie8 + 0 comments [deleted]maniraj_madishe1 + 0 comments I saw no such BST because BST strictly follows elements(root.left)

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

ksmukta + 0 comments 1 cannot go to the right of 4 as it will break the BST invariant

Piramidka + 0 comments [deleted]RodneyShag + 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.

saxtouri + 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); }

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

taieddie8 + 0 comments [deleted]holy_monk + 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; }

153J1A05A1 + 0 comments this doesn't work for all the test cases.

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

Sid1998 + 0 comments Beautiful!

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

knyl2013 + 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)

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

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

yashnisar + 2 comments It would be nice if the sample tree given in the example would be a Binary Search Tree. The example could mislead people to solve this problem for a Binary Tree.

RichArt + 0 comments I totally agree with you. It's a very unaccurate problem description.

donosonaumczuk + 0 comments Agree with you!

vedas + 1 comment Test case 2 is failing for me!! In case of A being parent of B, I've returned A.

yesudeep + 1 comment Here's my code:

def lca(root, a, b): node = root while node: if max(a, b) < node.data: node = node.left elif min(a, b) > node.data: node = node.right else: break return node

Does that help you?

miere00 + 0 comments I noticed people often see @RubenzZzZ's anwser (which is awesome, btw) and forget to +1 this one too... Non-recursive == less expensive!

newsbeidl + 3 comments As with so many challenges here, this is a terrible problem description. This is one of the worst. The "Lowest common ancestor" is not even defined! And the sole example just returns the root of the tree! Horrible, lazy, horrible problem description. Why doesn't HackerRank have standards on their problems? We should be allowed to VOTE on how well defined a problem is, otherwise we end up with problems like this one.

verboze + 0 comments Agreed. This one definitely needed better examples. Since we can't really ask for clarifications on the problems or can't see the test cases until after writing and executing our program, edge cases and clear definitions are paramount...

tduncan + 0 comments Yes. I knew what the LCA problem was already, but this question is really ment for people who aren't familiar with it yet, so they should have it spelled out. I was annoyed that the problem says nothing about how to handle duplicate values - if you have a tree full of 5's, do you put all the 5's on the left, all of them on the right, or balance it out somehow? I just assumed they didn't include such things in the tests and my code worked, but this should have been mentioned in the problem.

taieddie8 + 0 comments I agree. I was able to pass the test cases even though I had test ran it with an incorrect solution.

RodneyShag + 1 comment ### Efficient Java solution - passes 100% of test cases

From my HackerRank solutions.

Make sure to leverage the fact that this is a binary

**search**tree. We assume the tree has unique values.Runtime: O(log n) on a balanced tree

Space Complexity: O(1)I solve it iteratively since recursion would take O(log n) space complexity

static Node lca(Node n, int v1, int v2) { while (n != null) { if (n.data > v1 && n.data > v2) { n = n.left; } else if (n.data < v1 && n.data < v2) { n = n.right; } else { break; } } return n; }

Let me know if you have any questions.

kumarsurajsingh1 + 1 comment Only problem in #2 test case, Can you help me ..

static Node lca(Node root,int v1,int v2){ if(root==null){ return null; } if(root.data>v1 && root.data>v2) lca(root.left,v1,v2); if(root.data

RodneyShag + 1 comment Hi. I cannot read your code since part of it is missing. Try putting it in a code snippet as I did in my post and I will take a look.

Vikrant_Ch + 2 comments static Node lca(Node root,int v1,int v2) { if(root==null) return null; if(root.data>v1 && root.data>v2) { return lca(root.right,v1,v2); } else if(root.data<v1 && root.data<v2) { return lca(root.left,v1,v2); } else { return root; } }

Vikrant_Ch + 0 comments failing for teastcase #2

RodneyShag + 0 comments I think you're traversing the wrong side of the tree. If the value at the root is larger than both v1 and v2, you should traverse the

*root.left*instead of*root.right*

silentkevie + 0 comments Is there no oversight for questions? There are two ridiculous problems with this one.

1) The first example given is not a BST. So why include it in the problem at all when the statement starts off talking about BSTs?

2) An ancestor, by definition, is something from which another is descended. So it is impossible to be your own ancestor. Therefore Test Case #2 is wrong.

Is the point of HackerRank to solve interesting algorithmic questions or to beat you over the head with useless and/or wrong information?

a7n007 + 1 comment the example tree is not a bst.

i_love_ramen + 0 comments Yup, looks like HackerRank needs to do some QA on their questions.

max1994 + 1 comment failing test case 2 despite keeping the condition if v1 ancestor of v2 return v1.

rishabjain603 + 0 comments same here.so do you know now what's the problem?

aaditya_oza + 0 comments Can there be duplicate instances of an entry in the BST ? If yes, what's the strategy to insert them into the tree ?

piyush_v94 + 4 comments what if Node A is an ancestor of Node B, do we return A or its parent?

kamikaz1_k + 0 comments I'd imagine a node cannot be considered its own ancestor. So I would think that you would need to return the parent of A.

thisisjoelee + 0 comments A, which I think is wrong but seems to be what the problem is looking for.

sllavanya91 + 1 comment You will have to return node A, because for the Lowest common ancestor problem, every node is considered a descendant of itself.

So if A is an ancestor of B, your lowest common ancestor would have to be A. Hope this clarifies your question.

divyaaarthi + 1 comment i have returned A , but output is incorrect

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

divyaaarthi + 0 comments getting incorrect in testcase 2

Dharya + 0 comments return A

Sort 285 Discussions, By:

Please Login in order to post a comment