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.

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

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 :)

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

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

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.

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.

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.

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

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.

staticNodelca(Noderoot,intv1,intv2){Nodetemp=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;}elseif(temp.data<v1&&temp.data<v2){temp=temp.right;}else{returntemp;}}}

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

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.

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.

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.

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.

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

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.

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.

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

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 ?

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?

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?

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?

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.

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

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.

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.

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

Nodelca(Noderoot,intv1,intv2){returnroot;}

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

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.

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

## Binary Search Tree : Lowest Common Ancestor

You are viewing a single comment's thread. Return to all comments →

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

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

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 :)

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

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

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)

{

}

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

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.

great answer...

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.

Please explain why assigning it as root works but when used as Node

root,iit fails the test case 2.node * lca(node * root, int v1,int v2) { if(root==NULL) { return NULL; }

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.

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

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

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.

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

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

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

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

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?

Thanks!

Perfect solution! (y) :-)

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

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

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.

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

I came with exact this solution!

awesome solution:)

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

Elegant and simplistic solution. wow.

I vastly prefer this version! Simplicity and elegance.

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

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.

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

didmake that assumption, why this code: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.

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

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

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

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

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

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.

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

This is your tree. The answer code runs fine.

Hi, shouldn't the tree be like this:

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

Tree flase

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

This is wrong for the following input:

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

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.

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!

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

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

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.

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

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.

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

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.

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

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 :-

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

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 ?

This also works.

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?

same situation here, bro :/

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?

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?

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.

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

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

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

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

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

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

My solution was so convoluted.

Thank u!!

I think in this counter example it wouldnt work:

v1 is 1 and v2 is 7

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

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

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.

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

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.

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:

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

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

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,

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.this doesn't work for all the test cases.

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

Beautiful!

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.

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

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

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.

Brilliant solution!

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

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

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