RubenzZzZ 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; }
jitendrax [deleted]jitendrax [deleted]
rmccune 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 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 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 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 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 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 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 great answer...
pardeshi_kavita1 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.
Ru5h1bh thanks man!!
kalicharanvemuru 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
palashrawat7 Could you please explain it step by step.
amala9 [deleted]stark007_sc 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 BTW, you can always add print statements temporarily for debugging your own code.
isabelladom247 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.
benjamin_blocks1 Moderators please ban this user.
BlinkinBharg This will not pass the case where v1 is an ancestor of v2.
phillipnguyen 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 can u help me to bug what is wrong with testcase 2 for my code.
vidhi0007 If v1 is the ancestor of v2, then should the LCA = parent of v1 instead of v1?
StefanK 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 Agreed, it confused me too until I read your comment! Thanks :)
kapildevneupane1 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 Thanks!
divyaaarthi [deleted]
kiner_shah Perfect solution! (y) :-)
maverick55 couldn't think of a more perfect solution than this one.
RaviShekhar93 That is because, its the same as the code in Editorial Section
b0kater 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 I agree. Especially considering that this is clearly tail-recursive (which makes it trivial to convert to an iterative solution).
Mohit_Yadav_389 I came with exact this solution!
jaskaransingh_17 awesome solution:)
anujpriyadarshi This code gives the output as 1 and result is correct. In an another code output is 4 and then too result is correct.
Arun_Raj7 Elegant and simplistic solution. wow.
chesschingis I vastly prefer this version! Simplicity and elegance.
AdityaShinobi Instead of while(true) shouldn't we use while(temp)? Better to have Null checks ahead.
MK_khaldon 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
MarwaA 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.
WaduHekkk thanks dude
nguyencongbinhp1 it's a perfect solution!!
jonmcclung 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 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 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 i made throw(exception) assumption is wrong swapping everything in the beginning simplifies problem significantly
aru_674 not here certainly because i was getting WA in some test cases assuming v1
ejan16 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 man, at first sight I thought this would be more like a medium question... but after thinking it through... meh
Thrashans 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 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 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 8 / \ 4 9 / \ 1 6 / \ 3 2This is your tree. The answer code runs fine.
hongocvuong1998 Tree flase
coolrahuliit1501 what if current->data>v1&¤t->data
m_orazow This is wrong for the following input:
6 7 5 12 9 8 10 8 10
kartheek_kappag1 also wrong for below output 7 4 2 7 1 3 6 8 6 8
Mikeiyan 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.
Moghaak 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 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 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 you have given the end 'return root' in else condition where as it should be returned in every condition. just remove last else...
Moghaak 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.
zazublue00 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
abobakrpp 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 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 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 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 same situation here, bro :/
RJB3_MechLearn 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 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?
umerfarooq 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 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 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 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 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 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 That particular piece of logic would return false since the test 4<1 returns false and the test 4>7 returns false.
dgodfrey 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 Thank u!!
fede92 I think in this counter example it wouldnt work:
v1 is 1 and v2 is 7
4 / \ 2 6 \ / \ 3 5 7 / 1Answer we would get is 4 and the correct answer is 6.
alexmiragall [deleted]taieddie8 [deleted]
maniraj_madishe1 I saw no such BST because BST strictly follows elements(root.left)
thedurphy 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 1 cannot go to the right of 4 as it will break the BST invariant
Piramidka [deleted]
RodneyShag 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 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 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 [deleted]
holy_monk 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 <-- v2if 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 this doesn't work for all the test cases.
hingoman25 Can someone explain this recursive solution to me? I'm not able to get the correct return value.
Sid1998 Beautiful!
avansharma 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 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 why do you have return lca(root.right, v1,v2) as opposed to lca(root.right,v1,v2)?
timurig 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.
sam_littlefair Brilliant solution!
rajazzam22 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
janezz55 You should also have written, that you're doing a binary search for both values.
tao_lint has to consider the scenario when v1 or v2 equal to root.data
woldegebrielkeb1 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; }
Yu_Zhao1 Why are you smarter than me?
sarathy_v_krish1 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; }
appletopper1 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
appletopper1 - 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;
dukedavis Easiest solution https://www.youtube.com/watch?v=N9yepbXdOkI
appletopper1 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;} } } }appletopper1 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;
rmserradas Straight to the point. Cool, thanks for sharing this thought.
chengluchn 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".
susanmayer1506 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/
FaxMachin3 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
yogesh_sirsat_ hey man , how can you think like that its amazing
cyril_equilbec 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
yoav_vollansky 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.
lenhuang720 [deleted]lenhuang720 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; }
sdsatyakidas1995 [deleted]sdsatyakidas1995 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; }
salvatore_panno1 yes is exactly what I tought, the structure of the tree is already tell us how to proceed
yashnisar 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 I totally agree with you. It's a very unaccurate problem description.
donosonaumczuk Agree with you!
britain444 I did solve it for Binary Tree (correctly) :( The wrong image is not an excuse for not carefully reading the exercise description but I really was mislead by the image.
Btw, where is the right place for reporting such things so they can be fixed?
silentkevie 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?
andyp_wichmann Came here to upvote number 1. That should be updated.
shcallaway Yeah, the first diagram is misleading.
newsbeidl 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 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 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 I agree. I was able to pass the test cases even though I had test ran it with an incorrect solution.
lampuiho I have a question. Can root of either v1/v2 value itself be the common ancestor?
RodneyShag 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 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 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 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 failing for teastcase #2
RodneyShag 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
Sort 485 Discussions, By:
Please Login in order to post a comment