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.
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!
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!
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.
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
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.
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.
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.
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.
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.
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;
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.
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.
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)
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.
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.
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".
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.
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.
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
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?
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...!
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
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.
@@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).
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
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 ?
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.
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.
agree
OKK .. lets just appreciate his innocent smile!
This topic has confused me since 2 days. This is the best explanation I've found. Thank you sir :) Cleared all my doubts :)
Absolutely love the clear explanation and walkthrough. Thank you!
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.
The author is a genius. Thank you very much!
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!
Sir one thing i must say here , your videos and explanations are out of the box. Very easily anyone can get it. Thanks allot.
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!
Sir, I have watched many other people videos but your's are simply crystal clear
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
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.
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
Sure please post
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.
I agree
isnt it postorder as we are processing what to return after left and right.
@@cripz4203 postorder hai bhai, you are right.
It is inorder since we go leftmost,root and then right
No...its postorder.
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.
I love this guy, very clear explanation !!!
You are the best teacher sir thank you so much for all this solutions
i dont know how to praise you. i have less words to appreciate you..
Amazing explanation. Please make more videos on Algorithms.
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.
thanks for making things clear and simpler sir
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
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.
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.
You are simply amazing !. Keep the good work and spread the knowledge
No need for "else". Great code walkthrough and explanation !
Much appreciated!
can you explain it please
Bahut badhiya sir .... Maja a Gaya sir
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;
Yes this works perfectly for Binary Search Tree but I guess the code explained in the video is for Binary Tree :)
Very good explanation.I liked the reasoning in your videos.
Awesome explanation, great sir.
Clear explanation. Easy to understand
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.
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.
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)
really good method of explaining!!
This man is awesome. Thank you.
Sir amazing explanation
Can you please tell how is this inorder? Shouldn't it be preorder
Your explanation is awesome bro! Thank you! :)
so clear explanation!
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;
}
DAMM !!! ABSOLUTLY SPOT ON
Ur a amazing teacher
👍👍
@@vivekanandkhyade sir pls continue this lectures
Great Video...
PS-: can watch it at 4x comfortably
finally i understand how it works ! thank you very much !
Awesome video. Great explanation, keep up the good work sir!!
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.
Excellent explanation 👍
This solution not work when one of the two nodes is found and not the second one. So its return the founded node.
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.
the best!☺
No doubt in awesomeness of explanation!!
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.
yes and that too should be the answer
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".
whats the use of visiting h if we have already found d which is LCA.
@@raniajay0410 then how will you know whether "h" exists or not?
@@1388tushr Exactly. If one of the nodes is not present this algorithm will return the other node which is present
@@abcd1235911 this what i was thinking while i was watching this video, this algo is not completely correct
Thank you so much for all your video sir...
Thank you so much for great explanation
Great explanation!
You are godsent, thanks a lot!
Love you bro. You are so real!!
nice video.............................
well explained..
Liked and subscribed :) Thank u for explaination
sir your video is really awesome
Thanku ji
Nice explanation Thank you.
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.
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.
Good explanation
Best explanantion :) .Subscribed
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
best teacher
great job sir
Thank you
this is preorder traversal na sir?
Thank you so much sir!
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
same lol
VERY WELL EXPLAINED||
great explanation but i think this is pre order traversal
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?
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...!
It's just a corner case, but otherwise you've explained it very well..good job!
merci monsieur
good explanation sir, thanks :)
you used postorder traversal ... I think
yeah because he is returning after checking the values of both the children
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
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.
@@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).
@@gyanasahu1006 You meant pre, not in
i think u have used preorder traversal!!
Thanks bro
Love it ..!
Explain it for (j,c).... 🤨
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
You should have just returned node.value and kept something like -1 for a case where you dont find the node
when you are returning the value use .data or .key with the calling function
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 ?
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.
Should be pre-order instead of in-order.
What if one of the element is in the left branch of other ?
this solution will not work in case if B==root->node ans c is not present
nice !!
this is how the DSA faculty looks like!
Thank u
What if the root node is one of the two node ??
This won't work when one of the two nodes is not found.
10:08, I think you want to write "a", but not "LCA" ?
It's good
good. but a little bit slow. I need to see ur vdos at 2x speed
if LCA is not present it will return wrong answer.
make more videos plzzzzzzzzzzz :(