Hey tushar, can you please upload video about The Great Tree-List Recursion problem. I have been following your tree lectures and it is as always well explained except it misses one of the most asked interview problem.
Hii, You have a very cool way of teaching advanced data structures and algorithms, why don't you now have a go a competitive coding , it will be a huge boom to peeps.
if(root.data > Math.max(n1.data, n2.data)){ return lowestCommonAncestor(root.left,n1,n2); }else if (root.data < Math.min(n1.data,n2.data)){ return lowestCommonAncestor(root.right,n1,n2); }else{ return root; } Here in conditions we will compare with root.data not just root as one is value other is node.
Thanks for this video very helpful. Can you please have a video explaining the O(n) time suffix array construction using Karkaainen. Thanks in advance.
0:44 "looking for diverged in different paths and if one node is an ancestor of the..." But how the heck am I supposed to figure that out quickly in a coding interview?
Hi Tushar, You have condition like if (root > max (n1.date,n2.data)) , which max will return integer value and you are comparing with Node which is pointer so it will not compile code
Hi Tushar, nice explanation! One question - What if we got to check the existence of n1 and n2 in this tree? Consider they are not present, so this algo will return me an output. For ex: Node "-20" and Node "7" will return me Node "-10"..
Nope, this is O(N) solution as tree can be unbalanced, check out www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor for log solution.
Hello Tushar, Very simple and elegant Algo, Thanks. Just curious, If i give input as 30,79: 79 not being in tree, I will get 30. Is this a valid answer?
This doesn't consider the case where one or both of the elements doesn't exist in the tree. In case of the former, it will return the one that is present in the tree and not consider the other data (that DNE) at all.
i THINK THERE IS A MISTAKE IN THE CODE.....It shouldnt be the max of both node's data... the root node should be less than both of the n1 and n2....... Node lca(Node node, int n1, int n2) { if (node == null) return null; // If both n1 and n2 are smaller than root, then LCA lies in left if (node.data > n1 && node.data > n2) return lca(node.left, n1, n2); // If both n1 and n2 are greater than root, then LCA lies in right if (node.data < n1 && node.data < n2) return lca(node.right, n1, n2); return node; } this is correct....
![Tee Grizzley - Blow for Blow (feat. J. Cole) [Official Video]](http://i.ytimg.com/vi/wNLN5xsx5dc/mqdefault.jpg)
Your Explanation is awesome
Hey tushar, can you please upload video about The Great Tree-List Recursion problem. I have been following your tree lectures and it is as always well explained except it misses one of the most asked interview problem.
this has my vote as well
If Tushar can't convince Tushar then nobody can
Hii, You have a very cool way of teaching advanced data structures and algorithms, why don't you now have a go a competitive coding , it will be a huge boom to peeps.
Damn. The best method ever.
Awesome video, this solution is even more neat than the solution presented in "The Element of Programing Interview". Thanks!
Thanks for your video, it's very helpful.
if(root.data > Math.max(n1.data, n2.data)){
return lowestCommonAncestor(root.left,n1,n2);
}else if (root.data < Math.min(n1.data,n2.data)){
return lowestCommonAncestor(root.right,n1,n2);
}else{
return root;
}
Here in conditions we will compare with root.data not just root as one is value other is node.
yup that correction should be there,but is quite mindful anyways...
Thanks for this video very helpful. Can you please have a video explaining the O(n) time suffix array construction using Karkaainen. Thanks in advance.
0:44 "looking for diverged in different paths and if one node is an ancestor of the..." But how the heck am I supposed to figure that out quickly in a coding interview?
It should be root.data instead of root. :)
Yasss
Awesome Tushar. Great videos!
Hey Tushar, can you please make a video on treaps.
Thanks
Since all the give example are either greater or lesser than root node 10 so we know where to move..but what if we had ,-10 and 30 then how we move
Hi Tushar, You have condition like if (root > max (n1.date,n2.data)) , which max will return integer value and you are comparing with Node which is pointer so it will not compile code
In here may be if(root->data >(n1->data && n2->data)) will be in code.. But it's just for conception...
Ya i got it. Thanks
Small correction at first line-- > if(root.data > max(n1.data,n2.data))
Excellent. Thanks a lot.
Made it really lucid , Sir😎
Cool and simple solution!
Hi Tushar, nice explanation! One question - What if we got to check the existence of n1 and n2 in this tree? Consider they are not present, so this algo will return me an output. For ex: Node "-20" and Node "7" will return me Node "-10"..
Very helpful!
Hey Tushar, Excellent explanation.
Please upload some linked list related problems as well.
Why isn't the lowest common ancestor of (6,9) is -10
-10 is also common ancestor of 6 and 9, but it’s not the lowest. 8 is the parent of of 6 and 9. Hence it would be the LCA.
Can you please do a lesson on finding LCA of Bst without the parent pointer reference?Thank you
MNNITIANS like Here
Tushar, Can you make a video of "Word Square" question in LeetCode, which I think is one of the most difficult question in LeetCode.
Fantastic as always !
precise solution
eres un papu we
Thanks it helped me a lot with the italian computer science olimpics
Thanks alot, it's very easy to understand it.
Superb Solution. I tried modifying the solution for "Lowest Common Ancestor in Binary tree", but this ones even better
Thanks !
Thank You Tushar Roy you are an absolute beast
Thanks
Thanks Tushar! I like your explanation. Please make a video about quicksort.
mycodeschool has a very good video on quicksort if you still need it.
Thank you for making these videos.
thanks explained so well !!!
Hey tushar the complexity for the solution is log N right where N is no. of nodes
Nope, this is O(N) solution as tree can be unbalanced, check out www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor for log solution.
I think the return value of function should be Node *, not Node. We are returning pointer to a node, not actual node.
ashu singh In Java 'Node' is a reference and he writes the code in Java.
Best explanation I have seen!
This solution assumes that both n1 and n2 are present in the tree, right? Maybe its worth mentioning.
If n1 and n2 both are not present then still solution is valid. In that case nothing will be returned.
Keep doing the good work sir!!
This is really helpful!
Good job.Love ur videos :)
Awesome, simple super
Hello Tushar, Very simple and elegant Algo, Thanks. Just curious, If i give input as 30,79: 79 not being in tree, I will get 30. Is this a valid answer?
+arun vyas Also need to do null check, or items not present in tree.
+Tushar Roy Thank you Tushar.
Nice and crisp. TY
Really appreciate!!!!!!!
how does this code handles the last case i.e 30 and 78
It returns the root because it doesn't pass the condition at the node 30; (30)root < min(30, 78) since the minimum 30 isn't shorter but equal to 30.
This doesn't consider the case where one or both of the elements doesn't exist in the tree. In case of the former, it will return the one that is present in the tree and not consider the other data (that DNE) at all.
If the elements don't exist then how can their ancestor exist?
You check that condition before calling this function.
Thanks bhaiya!
Short & sweet
gr8
Beautiful!
cool
i THINK THERE IS A MISTAKE IN THE CODE.....It shouldnt be the max of both node's data... the root node should be less than both of the n1 and n2.......
Node lca(Node node, int n1, int n2)
{
if (node == null)
return null;
// If both n1 and n2 are smaller than root, then LCA lies in left
if (node.data > n1 && node.data > n2)
return lca(node.left, n1, n2);
// If both n1 and n2 are greater than root, then LCA lies in right
if (node.data < n1 && node.data < n2)
return lca(node.right, n1, n2);
return node;
}
this is correct....
10 is a common ancestor to 30 and 78, so the lowest common ancestor should be 10, not 30.