Lowest Common Ancestor Binary Search Tree

/ tusharroy25
github.com/mis...
github.com/mis...
Find lowest common ancestor in binary search tree.

[@ruitu6005]

Awesome video, this solution is even more neat than the solution presented in "The Element of Programing Interview". Thanks!

[@Simply_maniyaa]

Superb Solution. I tried modifying the solution for "Lowest Common Ancestor in Binary tree", but this ones even better

[@TusharMudgal]

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.

[@ruitu6005]

this has my vote as well

[@arvindhmani06]

If Tushar can't convince Tushar then nobody can

[@deepak-ui5li]

Thank You Tushar Roy you are an absolute beast

[@davidenunin886]

Thanks it helped me a lot with the italian computer science olimpics

[@itsnpe]

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.

[@_PRITIJHA]

Your Explanation is awesome

[@harishdoddi322]

Awesome Tushar. Great videos!

[@MrityunjayRanjan]

Small correction at first line-- > if(root.data > max(n1.data,n2.data))

[@prekshakoirala6331]

Damn. The best method ever.

[@fabricator.cap.hill.seattle]

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?

[@abhishekshaw9861]

Made it really lucid , Sir😎

[@dragoxofield]

Best explanation I have seen!

[@manofacertainrage856]

Thank you for making these videos.

[@ivsaimanoj]

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

[@debajitsaikia1]

Hey Tushar, Excellent explanation. Please upload some linked list related problems as well.

[@ashusingh4937]

I think the return value of function should be Node *, not Node. We are returning pointer to a node, not actual node.

[@egor.okhterov]

ashu singh In Java 'Node' is a reference and he writes the code in Java.

[@ernestina475]

Can you please do a lesson on finding LCA of Bst without the parent pointer reference?Thank you

[@mcw0805]

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.

[@maaz3587]

If the elements don't exist then how can their ancestor exist?

[@egor.okhterov]

You check that condition before calling this function.

[@niachungdupit8104]

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

[@kaushikjp]

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

[@jahirulislammonir3490]

In here may be if(root->data >(n1->data && n2->data)) will be in code.. But it's just for conception...

[@kaushikjp]

Ya i got it. Thanks

[@algorithmicthoughts8565]

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.

[@deepanshugarg4713]

Hey Tushar, can you please make a video on treaps. Thanks

[@eugeniaqing]

Thanks for your video, it's very helpful.

[@SC-uv5le]

Cool and simple solution!

[@judemartin8369]

Fantastic as always !

[@ivaylopankov7369]

This solution assumes that both n1 and n2 are present in the tree, right? Maybe its worth mentioning.

[@codeonmars579]

If n1 and n2 both are not present then still solution is valid. In that case nothing will be returned.

[@kushaladhvaryu]

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.

[@angshumansarma2836]

yup that correction should be there,but is quite mindful anyways...

[@kautukraj]

Very helpful!

[@Miss_iryna_]

Thanks Tushar! I like your explanation. Please make a video about quicksort.

[@prekshakoirala6331]

mycodeschool has a very good video on quicksort if you still need it.

[@RafiqulIslam-je4zy]

Excellent. Thanks a lot.

[@saptarshimitra1267]

Nice and crisp. TY

[@emersonmicu1683]

Thanks alot, it's very easy to understand it.

[@siddharthsethia5986]

Keep doing the good work sir!!

[@诸葛俊伟]

Tushar, Can you make a video of "Word Square" question in LeetCode, which I think is one of the most difficult question in LeetCode.

[@arunvyas27]

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?

[@arunvyas27]

+arun vyas Also need to do null check, or items not present in tree.

[@arunvyas27]

+Tushar Roy Thank you Tushar.

[@AshutoshKumar-il3wk]

thanks explained so well !!!

[@TheCowsrkewl]

This is really helpful!

[@rashmithkoundinya]

Hey tushar the complexity for the solution is log N right where N is no. of nodes

[@vitaly4097]

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.

[@Bakepichai]

Short & sweet

[@MoharnabSaikia]

Good job.Love ur videos :)

[@MountCook]

Beautiful!

[@MrThepratik]

precise solution

[@jimmy1681000]

Really appreciate!!!!!!!

[@sivakishorejaladi3482]

Awesome, simple super

[@priyadarshanr296]

Why isn't the lowest common ancestor of (6,9) is -10

[@nikhilkv5564]

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

[@SaurabhSingh-db8xq]

Thanks bhaiya!

[@pragyamukherjee8243]

Thanks !

[@deepakbammi3967]

It should be root.data instead of root. :)

[@ayushgarg5929]

Yasss

[@abhisekhagarwala9501]

how does this code handles the last case i.e 30 and 78

[@meikelk882]

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.

[@abhisheksharma3553]

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

[@akashreddy7725]

Thanks

[@TejasPatil-lu6zf]

cool

[@chiquiro10]

eres un papu we

[@goloth]

10 is a common ancestor to 30 and 78, so the lowest common ancestor should be 10, not 30.

[@nishithakur424]

gr8

[@adarshsharmanit356]

MNNITIANS like Here