It is easy to go through, and everything is so nice, besides if the binary tree contains Integer.MAX_VALUE layer, for example, the call stack may be passing away.
you probably dont give a damn but does any of you know of a way to log back into an Instagram account?? I was stupid lost the login password. I would love any tips you can give me
Too good explanation. short and sweet. I can say this particular solution is way better explained than Back ToBack SWE. Thanks and appreciate your effort...
Optimization note, if the left subtree search yielded the LCA, there's no need to search the right subtree. This can only be avoided by keeping track of how many of the target nodes have been found; it's not sufficient to check if the left subtree search returned a node that is not one of the target nodes, because one of the target nodes may as well be the LCA. For example, 6, and 2.
The recursive approach uses far more space than finding the paths to the nodes. In terms of space efficiency the approach taken in the first two minutes is actually more efficient!
Great work, as you recommended I started solving problems on GeeksForGeeks, your videos + that website together make up a great learning experience thanks again, keep up the good work !
I was asked this question in an interview, with 2 special conditions as the follow-up: 1. The given 2 TreeNodes are NOT guaranteed to be on the tree. 2. If either or neither of them is on the tree, it is required to return null.
@@harshsahu7825 that's pretty bad then. The worst algorithm I can think of just at the top of my head is to search the tree for the first node n1, then for the second one n2 and if either one wasn't found, then return null. If both were found, run the same algorithm that was explained in this video. In total, this algorithm has time complexity of O(n+n+n)=O(n). It could definitely be optimised
Thank you so much for your contribution..I think it is one of the best lectures i have ever seen for like this focusing on interview problems alone..Again thank you so much...please keep on share more and more challenging problems
in the last 8,7 example, is there an assumption that both given nodes whose ancestor we are looking for, have to be present in the tree? bcoz we returned 8, and never went down to 7 to see if it was actually there or not
I think we should make assumptions clear that is both nodes should exist and nodes are not equal, tree with one node etc? static Node lca(Node rootNode, int a, int b, AtomicBoolean found) { if (rootNode == null) { return null; } if (found.get()) { return null; } Node left = lca(rootNode.left, a, b, found); Node right = lca(rootNode.right, a, b, found); if (left != null && right != null) { found.set(true); return rootNode; } final boolean rootMatched = rootNode.i == a || rootNode.i == b; if (rootMatched) { if (left != null || right != null || a == b) { found.set(rootMatched); } return rootNode; } if (left != null) { return left; } else if (right != null) { return right; } else { return null; } } This should work for all the cases. I used AtomicBoolean but can be replaced by MutableBoolean. You have a match only when found returns true.
I saw the solution to this problem over gfg but couldn't get the part of searching even after we were using maps for given 2 values... thnx for your question.. helped me alot
Even if we traverse until node 7, it would eventually return the same value 8 to the root of the tree. This case holds true every time when one of the nodes is a ancestor.
Very well explained. Small correction required in your code, instead of doing nodes equals comparison using '==', you need to do node data comparison as shown below. if(root.data == n1.data || root.data == n2.data){ return root; }
That doesn't need to be corrected. The value is irrelevant. Node n1 and n2 hold the address of the nodes that need to be found. All you need to do is compare the address.
I think the method you explained above is based on the assumption that both n1 and n2 are present Can you please explain what if one of the two or both nodes aren't present in Binary tree Thanks in Advance
I checked various sites, even during interviews of big companies & everywhere the same kind of solution is given & I have following issues with this problem & I wonder that why people don't raise this concern, either they don't understand English or they are just interested in clearing the interviews to get the money - a) How can you assume that both nodes are present in the tree without saying it anywhere. b) Because above assumption is missing then you might be returning wrong answer even if there is not common ancestor, rather we should say that one or both the given nodes not found. c) When you use some other language's word in your problems then respect the meaning of that word also or don't use that word at all. How can I be my own ancestor in any condition, so how can 8 be its own ancestor. So if you have different definition then use different word also, say like find the common meeting point etc. But using the word 'Ancestor' here is not right. Improvement - If we follow the correct definition of Ancestor then we can apply the same solution to find the common ancestor for multiple nodes. Assumption : All nodes in the tree are unique.
Thank you . Good one . You are awesome. from 10.55 the way you talked, looks like u are iterating an array ['like', 'share', 'subscibe'] + 'this video'
I think the command wriiten in 3rd line should be after 5th line.This would cover all the test cases and we would not be needed to make any assumptions.
won't this solution will fail for a skewed tree where one node does not exist. for example LCA(3,8) in this tree (null denoted by #) : 1 /\ # 2 /\ # 3 /\ # 4 Expected output: null Actual output : 3
came here after trying to read and failing to understand the leetcode editorial on this question. this was a fantastic explanation, thank you.
Recursion is indeed a divine art
It is easy to go through, and everything is so nice, besides if the binary tree contains Integer.MAX_VALUE layer, for example, the call stack may be passing away.
you probably dont give a damn but does any of you know of a way to log back into an Instagram account??
I was stupid lost the login password. I would love any tips you can give me
@Kylan Ali instablaster =)
the way this was explained in 11 min. I don't think i can find more valuable solutions for this in such a short time anywhere else. Amazing!
After i get tired of the logics and code explained by everyone, i do watch your video to understand it in layman and practical way.
I love this guy's multiple walking-through examples on white board!
The space complexity of both the algorithms is O(height), because the recursive algorithm will have function calls on the stack.
Wow, great explanation about the algorithm! I appreciated the fact that you gave multiple examples that tested different things!
Best Video on LCA available on UA-cam, Thanks Tushar!
The other solution also takes the implicit stack during recursion, so yes it does require the extra space.
Too good explanation. short and sweet. I can say this particular solution is way better explained than Back ToBack SWE. Thanks and appreciate your effort...
Yes u r correct
Optimization note, if the left subtree search yielded the LCA, there's no need to search the right subtree. This can only be avoided by keeping track of how many of the target nodes have been found; it's not sufficient to check if the left subtree search returned a node that is not one of the target nodes, because one of the target nodes may as well be the LCA. For example, 6, and 2.
ASSUMTION:
We may assume that either both n1 and n2 are present in the tree or none of them are present.
NOTE : optimisation not works for special case
Thank you for covering multiple cases. Other videos didn’t explain as thoroughly as you and didn’t go through many test cases
This is a very useful, well explained, and simple algorithm. Thank you, Tushar.
Thank you! Finally a video that helped me understand the recursive details of the various cases of binary tree
Can't agree more
Another great explanation with a beautiful solution!
After 5 years he's still helping
Yep
tera naam mast hai
@@prelimsiscoming thanks..
Thank you, sir! I was confused about this recursive code, but now I understand how it works perfectly!
Last example is really important to explain both nodes in the same path.
This was a great visual walkthrough. Clear and concise.
Nicely explained. This is a popular problem statement in Amazon interviews.
Excellent video/explanation. Your videos make algorithms so much easier.
You are videos are just awesome! Great job! Can't imagine prep without your videos!
Great job Tushar! Absolutely awesome walkthrough..
Six years later and im still learning from you
The recursive approach uses far more space than finding the paths to the nodes. In terms of space efficiency the approach taken in the first two minutes is actually more efficient!
Your explanation always hits the spot. Thanks :)
man, your hair style and explanation a true entertainer!!
Hahahaha !!! He’s cool tho
Thank you sir for this dry run feeling lucky to find this video ... Keep making such dry run video sir Thank you
Thanks for the great explanation
hi Thushar, so nice of you...explained very well
thank you so much this is the most helpful video ive found for this question
Clear and straight to the point.
great explanation! this dry run really helped me a lot
Excellence! Real knowledge, thank you.
Great work, as you recommended I started solving problems on GeeksForGeeks, your videos + that website together make up a great learning experience thanks again, keep up the good work !
In the recursive solution isn't anyway space is consumed due to stacks
yes, obviously .. space complexity is O( h ) .. worst case will occur when the tree is skewed and the ancestor lies beneath of it.
Love your explanations Tushar! You are awesome!
Recursion Explained nicely, thanks
best lca video in youtube so far!
Great explanation as usual!
I was asked this question in an interview, with 2 special conditions as the follow-up:
1. The given 2 TreeNodes are NOT guaranteed to be on the tree.
2. If either or neither of them is on the tree, it is required to return null.
I can do that in n^2. whats your approach?
@@harshsahu7825 that's pretty bad then. The worst algorithm I can think of just at the top of my head is to search the tree for the first node n1, then for the second one n2 and if either one wasn't found, then return null. If both were found, run the same algorithm that was explained in this video. In total, this algorithm has time complexity of O(n+n+n)=O(n). It could definitely be optimised
@@agfd5659 he is just a bad teacher lol, realized a bit later
Thank you so much for your contribution..I think it is one of the best lectures i have ever seen for like this focusing on interview problems alone..Again thank you so much...please keep on share more and more challenging problems
Awesome video! Your explanation is too good. I can understand recursion very easily through your video.
great explanation, you have high-quality videos..thanks.
in the last 8,7 example, is there an assumption that both given nodes whose ancestor we are looking for, have to be present in the tree?
bcoz we returned 8, and never went down to 7 to see if it was actually there or not
I think we should make assumptions clear that is both nodes should exist and nodes are not equal, tree with one node etc?
static Node lca(Node rootNode, int a, int b, AtomicBoolean found) {
if (rootNode == null) {
return null;
}
if (found.get()) {
return null;
}
Node left = lca(rootNode.left, a, b, found);
Node right = lca(rootNode.right, a, b, found);
if (left != null && right != null) {
found.set(true);
return rootNode;
}
final boolean rootMatched = rootNode.i == a || rootNode.i == b;
if (rootMatched) {
if (left != null || right != null || a == b) {
found.set(rootMatched);
}
return rootNode;
}
if (left != null) {
return left;
} else if (right != null) {
return right;
} else {
return null;
}
}
This should work for all the cases. I used AtomicBoolean but can be replaced by MutableBoolean.
You have a match only when found returns true.
I saw the solution to this problem over gfg but couldn't get the part of searching even after we were using maps for given 2 values... thnx for your question.. helped me alot
Even if we traverse until node 7, it would eventually return the same value 8 to the root of the tree. This case holds true every time when one of the nodes is a ancestor.
this algo is based ln the assumption that that both nodes will be present in the tree...nice observation btw
4 years ago....damn
Very nice explanation with the examples!
It's much clear now. Thanks a lot for your explanation.
Amazing explanation!!!
Awsome Explanation Bro!!
Very lucid explanation
Your solutions are amazing!! Keep doing it :)
Excellent explanation! Hats off!
Your second algorithm has also O(n) space complexity!!! You can't neglect the function stack calls.
I have become a fan! Great work Sir :)
Very well explained. Small correction required in your code, instead of doing nodes equals comparison using '==', you need to do node data comparison as shown below.
if(root.data == n1.data || root.data == n2.data){
return root;
}
That doesn't need to be corrected. The value is irrelevant. Node n1 and n2 hold the address of the nodes that need to be found. All you need to do is compare the address.
Genius approach...well explained
Nice explanation sir...really good video
Thank you so much, Tushar!!
I think the method you explained above is based on the assumption that both n1 and n2 are present
Can you please explain what if one of the two or both nodes aren't present in Binary tree
Thanks in Advance
its given in the question that both n1 and n2 will always be there in the tree.
you have given best explanation..thanks a lot
Very nicely explained! Thanks.
Really really helpful.
amazing!! Thanks Tushar! PLease continue!
above & beyond awesomeness!
Thanks a lot. You gave me the idea to solve this problem
Great explanation! Thank you for the video.
Thank you for the explanation. Very helpful.
Great job, the explanation is very clear and lucid. Thanks a lot :).
beautiful explanation!
Here we assume that both nodes are present. If one of them is not present, we return a wrong output.
ek like to banta hain, solid explanation hain
I checked various sites, even during interviews of big companies & everywhere the same kind of solution is given & I have following issues with this problem & I wonder that why people don't raise this concern, either they don't understand English or they are just interested in clearing the interviews to get the money -
a) How can you assume that both nodes are present in the tree without saying it anywhere.
b) Because above assumption is missing then you might be returning wrong answer even if there is not common ancestor, rather we should say that one or both the given nodes not found.
c) When you use some other language's word in your problems then respect the meaning of that word also or don't use that word at all. How can I be my own ancestor in any condition, so how can 8 be its own ancestor. So if you have different definition then use different word also, say like find the common meeting point etc. But using the word 'Ancestor' here is not right.
Improvement - If we follow the correct definition of Ancestor then we can apply the same solution to find the common ancestor for multiple nodes. Assumption : All nodes in the tree are unique.
Very nice explanation thank you sir
Very nice Explanation.
Problem is what happens if only one of the given nodes is present and other is missing
Code fails 😥
The amazing Tushar. Thanks!
@Tushar: Good work and good explanations.
Genius. Thank you very much.
finally good explanation. I understand it now
Tushar is the best!
Excellent Explaination
Thank you for the video. One feedback I have is that the mic is too hard for the ears
Perfect. Thank you.
Great videos dude. Thanks!
Very nice and Clear Explanation ..Thanks for the Video.
No bro
Great explanation! Thank you.!
Awesome Explanation!
Great explanation, Thanks a lot
i really love this guy
complexity can be O(logn) since it is a binary tree
Thank you . Good one . You are awesome. from 10.55 the way you talked, looks like u are iterating an array ['like', 'share', 'subscibe'] + 'this video'
Thanks for the video, really helpful
In this algorith the 2nd last line "if(left==NULL && right==NULL) return NULL;" is not required as last line will return NULL if both are NULL.
Nice explanation, thank you sir.
God bless you man!
Wow! Great explanation!
I think the command wriiten in 3rd line should be after 5th line.This would cover all the test cases and we would not be needed to make any assumptions.
Thank you very much.....! Super solution!!!
which is better this approach or binary lifting?
won't this solution will fail for a skewed tree where one node does not exist. for example LCA(3,8) in this tree (null denoted by #) :
1
/\
# 2
/\
# 3
/\
# 4
Expected output: null
Actual output : 3