Lowest common ancestor of two nodes in Binary Tree Algorithm

[@Kaushikvel]

Some of the best things about your video, 1. your slow explanation. 2. code walk through 3. Complete explanation with lots of examples. Thank you.

[@parthobala7251]

agree

[@tanmayagarwal8513]

OKK .. lets just appreciate his innocent smile!

[@vardaanbajaj3181]

This topic has confused me since 2 days. This is the best explanation I've found. Thank you sir :) Cleared all my doubts :)

[@sjwang3892]

Absolutely love the clear explanation and walkthrough. Thank you!

[@sagarmalshankhala6826]

Sir ji, apka teaching ka FAN ho gya hu me to .. love you. Some of the best things about your video, 1. your slow explanation. 2. code walk through 3. Complete explanation with lots of examples.

[@ivantishchenko4686]

The author is a genius. Thank you very much!

[@___vandanagupta___]

i was not able to understand this question's solution from any other video but your simple explanation worked and i will never forget this solution again, thanks so much sir!

[@uncletom321]

I rarely subscribe to channels, but I did for yours because of how great your teaching method is. It has really helped me better understand data structures and algorithms. Thanks!

[@sushmanthnatha4019]

Sir, I have watched many other people videos but your's are simply crystal clear

[@aishwaryadwani9365]

Sir one thing i must say here , your videos and explanations are out of the box. Very easily anyone can get it. Thanks allot.

[@Dizzydizzydizzy7]

usually i have a hard and long time understanding these kinds of videos, but your videos are so clear I feel like even a toddler can understand

[@bajracha]

Thank you so much for such a clear explanation. Your explanation not only taught me how to understand walking through the algorithm but it actually taught me how to think about a solution and how to approach the solution. Thanks again.

[@sharmapeeyoosh]

Hello, Thanks for explaining so well, In your logic for finding out LCA works fine if both the nodes are present and both the nodes are part of different sub tree. Two situation does not handle in this code. 1) if either of the node is not present in tree itself 2) if second node is part of subtree of first node. for exm, P and L nodes. If user enters these two nodes then this algorithm will not work. Solution algorithm: 1) Both the nodes must present in tree otherwise print error and return. 2) if left and right returns non NULL, this is LCA. Print LCA and return NULL. 3) if second node is in subtree of first node then only first node we will return till root node. in such case main function shall have a piece of code, if final return is non NULL then this is the LCA, print LCA. I can post the code if someone needs. thanks

[@deliveringIdeas]

Sure please post

[@user-uh4be8ci7i]

You are the best teacher sir thank you so much for all this solutions

[@YSSP4]

Awesome video. Your explanations are simple and clear to understand. Please keep up the good work. For others, just like me if you are bothered about corner case where one of the element is not present in the tree, then try postorder traversal instead of inorder traversal so that you look in to both left and right nodes before coming to root node.

[@sandeepnallala48]

thanks for making things clear and simpler sir

[@adaz2724]

I love this guy, very clear explanation !!!

[@ishanpand3y]

Sir, I think this is preorder traversal. Because in inorder traversal first we go left then node then right, while in preorder traversal first we go node then left and then right.

[@marioburgos8656]

I agree

[@cripz4203]

isnt it postorder as we are processing what to return after left and right.

[@utkarshsingh4456]

@@cripz4203 postorder hai bhai, you are right.

[@bismeetsingh352]

It is inorder since we go leftmost,root and then right

[@rohitjadhav512]

No...its postorder.

[@harshshukla3358]

sir this is a very good explanation, just one point that you should have told that we are taking the assumption that both the nodes exist in the tree

[@daspradeep]

good explanations, got tripped by the edge case a bit because this assumes both nodes to be present in the tree, which is fine i guess. In case one of the nodes is not there then it fails.

[@shashwatagrawal8412]

Amazing explanation. Please make more videos on Algorithms.

[@RavinderSingh-nh6th]

i dont know how to praise you. i have less words to appreciate you..

[@bogdandumitrescu8987]

No need for "else". Great code walkthrough and explanation !

[@vivekanandkhyade]

Much appreciated!

[@RamKumar-kz8gg]

can you explain it please

[@hritikagarwal7676]

It would be far better if you also explain the intuition to this solution. Knowing the algorithm makes half of the work but knowing what led to this algorithm will make the solution video totally worthy.

[@shwetadk1986]

You are simply amazing !. Keep the good work and spread the knowledge

[@dipakkumarsinha5811]

Bahut badhiya sir .... Maja a Gaya sir

[@sampathmethuku7428]

very good explanation , but I think if the any one node either p or q does not exists then your code will fail, we expect to return null as one node is not present in tree. but your code returns the existing value.

[@shadesofspice5315]

Clear explanation. Easy to understand

[@anty_07]

A somewhat concise solution which uses the property of BST - LCA's value WILL fall between the the two given nodes. SO you keep going left from root till both the nodes values are less than current node , and keep going right till both value are greater than current value. Below is the code. while(root.data < v1 && root.data < v2){ root = root.right; } while(root.data > v2 && root.data > v1){ root=root.left; } return root;

[@vm1662]

Yes this works perfectly for Binary Search Tree but I guess the code explained in the video is for Binary Tree :)

[@andreeachirita9801]

really good method of explaining!!

[@nishantprajapati7166]

Awesome explanation, great sir.

[@gouravsharma2755]

Very good explanation.I liked the reasoning in your videos.

[@4yt158]

Your explanation is awesome bro! Thank you! :)

[@danielshalam2258]

finally i understand how it works ! thank you very much !

[@krishnavasani26]

Awesome video. Great explanation, keep up the good work sir!!

[@abhishekkumargupta3043]

This man is awesome. Thank you.

[@user-nd2lf7ss4x]

so clear explanation!

[@angadrajsingh4311]

Sir amazing explanation

[@rishabhjain4546]

Great Video. Thank you sir. What happens in the case when there is only one value present in the tree, and the other value is not. In that case, the algorithm is not working.

[@pi_by_2224]

try this approach struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) { if (p->valval && q->valval) return lowestCommonAncestor(root->left,p,q); if (p->val>root->val && q->val>root->val) return lowestCommonAncestor(root->right,p,q); return root; }

[@kartikaygoel3042]

Great Video... PS-: can watch it at 4x comfortably

[@alokdeshpande5517]

Excellent explanation 👍

[@HoanNguyen-fc8vb]

Thank you for your tutorial. You are one of the best so far. For the if(left !=null && right = null) return root. Is that right or (right !=null) .Please explain. Thank you very much.

[@beaglesnlove580]

Ur a amazing teacher

[@vivekanandkhyade]

👍👍

[@vishalplayzz2580]

@@vivekanandkhyade sir pls continue this lectures

[@ayushmishra3388]

I think so this algorithm will fail when there are multiple occurrences of n1 and n2, @8:06 pause the video see the tree, and replace the following nodes: *h with m, i with r, e with r.* after first finding m and r, node "D" becomes LCA and returns itself to "B", then "B" checks on its right, it finds "R", now on left of "B" we have "D" as LCA and on right of "B" we have "R" as LCA, so it will return "B" as LCA which is wrong, LCA Should have been "D" only.

[@GauravKawatrakir]

This solution not work when one of the two nodes is found and not the second one. So its return the founded node.

[@Sudarshansridhar]

what if the one of node given to find lca is not present in the tree? i think this solution holds good for both values are present. (if i am not wrong)

[@swj_69420]

Can you please tell how is this inorder? Shouldn't it be preorder

[@aparna123pathak]

No doubt in awesomeness of explanation!!

[@PIYUSH-lz1zq]

DAMM !!! ABSOLUTLY SPOT ON

[@thecreative9102]

Thank you so much for great explanation

[@payalsagar1808]

the best!☺

[@rohinirt6362]

Thank you so much for all your video sir...

[@1388tushr]

How about LCA of "f" and "j"? I think once the code hits "f", it will return "f", it won't go to its child.

[@lavishgarg4274]

yes and that too should be the answer

[@natesh1]

Awesome vids, can u please consider categorizing ur vids into playlists, for new watchers it helps a lot, otherwise they would have to keep scrolling all ur vids.

[@lokeshnegi5051]

well explained..

[@chetannikam8129]

nice video.............................

[@nikhilkumarmishra1225]

You are godsent, thanks a lot!

[@GROW_WITH_GBT]

Thanku ji

[@7Critics]

Great explanation!

[@unboxingzindagi9972]

Love you bro. You are so real!!

[@sayalishelke9597]

Best explanantion :) .Subscribed

[@neetisharma3768]

Liked and subscribed :) Thank u for explaination

[@anupkmr03]

Nice explanation Thank you.

[@vivekmit]

Good explanation

[@jagritbhupal5836]

Thank you

[@rajnikushwaha1459]

sir your video is really awesome

[@VenkatGonu]

code doesn't work if one of the node is not present, ideally it should return null but it returns the other node which is found

[@borisa6952]

Thank you for the explanations. I would like to know how to compute and write the algorithm of the "distance between the node e and node i" in this binary tree.

[@borisa6952]

I mean how to write the algorithm between two nodes (not root node) in a binary. The example with nodes e and i would be useful for me. Thank you in advance.

[@arpitverma8060]

VERY WELL EXPLAINED||

[@radhakantaghosh7295]

Hi, Does this method will work for "d" and "h" ? ..........what i am thinking is once execution hit "d" then, it will return that node and will never visit "h".

[@raniajay0410]

whats the use of visiting h if we have already found d which is LCA.

[@1388tushr]

@@raniajay0410 then how will you know whether "h" exists or not?

[@abcd1235911]

@@1388tushr Exactly. If one of the nodes is not present this algorithm will return the other node which is present

[@RohanSingh-bl5ho]

@@abcd1235911 this what i was thinking while i was watching this video, this algo is not completely correct

[@kabboghosh1853]

best teacher

[@TS-ku2lg]

Thank you so much sir!

[@sumitkumar-wp4xd]

great job sir

[@tassda2787]

merci monsieur

[@sunnyjain630]

i think u have used preorder traversal!!

[@sakshamagarwal6852]

good explanation sir, thanks :)

[@pradeepsingh-cg8iv]

Thanks bro

[@jamesqiu6715]

you used postorder traversal ... I think

[@samaryadav7208]

yeah because he is returning after checking the values of both the children

[@gyanasahu1006]

It is Inorder traversal, as we first check with the current node and return if it is equal to either one. If not equal we expand search to left subtree and right subtree

[@badsum]

Actual result comparison happens after both, left and right, return. It is post order. Also, if checking current node first for the result comparison, it should be pre-order, not in-order.

[@charismatic1516]

@@badsum Actually, there is both pre and post happening. However, in terms of logic, we check for LCA condition for the current node before checking it left and right subtrees, hence pre. We also do some checking/processing after the children processing. Similar example is when we want to do a sum of all root to leaf paths. In the recursive function, we first add node val to sum so far, then check if we reached a leaf (pre) then return sum, else get sums from left and right child, then add and return those sums (some post).

[@charismatic1516]

@@gyanasahu1006 You meant pre, not in

[@abhishekkarn8918]

this is preorder traversal na sir?

[@harirahul7703]

great explanation but i think this is pre order traversal

[@oneworldofstem7724]

I wonder when you first encounter this question, how do you figure out the possible steps for getting the answer? I am having trouble of algorithm questions recently. Very hard for me to think of the answer

[@gauravburjwal.98]

same lol

[@AshokBathini]

If one of the nodes p or q does not exist in the Binary Tree, this function will still return the node which is found, but it should have returned NULL. Am I right?

[@vivekanandkhyade]

yes Ashok , u r right.....Due to the restriction of space on board , I have just focused on the main condition.....in the code we can modify for this corner condition.....Thanks for helping me get better...!

[@AshokBathini]

It's just a corner case, but otherwise you've explained it very well..good job!

[@ayushthakur733]

Explain it for (j,c).... 🤨

[@adityachauhan1182]

this solution will not work in case if B==root->node ans c is not present

[@ricardosmith3752]

What if one of the element is in the left branch of other ?

[@SaurabhSingh-ch6nc]

Love it ..!

[@prajakta_patil]

Thank u

[@mdsaif4696]

In my interview, the question asked me to return int value.. not node value.. this method just messed.up. pls explain what to do if the function demands returning int value

[@ShivangiSingh-wc3gk]

You should have just returned node.value and kept something like -1 for a case where you dont find the node

[@ShubhamKumar-oh3jt]

when you are returning the value use .data or .key with the calling function

[@ayushthakur733]

What if the root node is one of the two node ??

[@jingli2168]

Should be pre-order instead of in-order.

[@SaurabhSingh-ch6nc]

this is how the DSA faculty looks like!

[@adityaojha2701]

It's good

[@ruchirai5775]

nice !!

[@suryajena1575]

This won't work when one of the two nodes is not found.

[@TechnicalBaniya]

sir for node k the ancestors are f,c,a and the ancestors of node f are c,a then the common ancestor should be c of nodes k and f but you said the common ancestor is f ?

[@vivekanandkhyade]

the lowest common ancestor for parent and its child is the parent itself. I am sorry i have not explained this in the video. I will reply tomorrow again with a more convincing proof. Thanks.

[@hellochii1675]

10:08, I think you want to write "a", but not "LCA" ?

[@bigjforever]

good. but a little bit slow. I need to see ur vdos at 2x speed

[@ridimamittal4064]

make more videos plzzzzzzzzzzz :(

[@zeref6437]

if LCA is not present it will return wrong answer.