Lowest Common Ancestor Between 2 Binary Tree Nodes (A Recursive Approach)
Vložit
- čas přidán 25. 07. 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Given the root of a binary tree and 2 references of nodes that are in the binary tree, find the lowest common ancestor of the 2 nodes. The nodes do not have parent pointers.
The Approach
So there are many modulations of this problem where you can build a hashtable and make parent pointers, etc. We will focus on the recursive solution.
The Algorithm
The key is that we want to root ourselves at a node and then search left and then right for either of the 2 nodes given.
If we see either node, we will return it, if we do not find the node in a subtree search the value of null will be returned and bubbled up.
After we search both left and right we ask ourselves what our results mean.
If we found nothing to the left, we just bubble up what is on the right (whatever that search result may be). This node we sit at cannot be the LCA since the left and right did not yield the 2 nodes we want.
If we found nothing to the right, we just bubble up what is on the left (whatever that search result may be). This node we sit at cannot be the LCA since the left and right did not yield the 2 nodes we want.
If both the right and left result are not null, we have found our LCA.
Why?
We know it is an ancestor at the least but we definitely know it is the lowest common ancestor because we went bottom upwards, whatever we hit will be the LCA and it will bubble up.
Complexities
Time: O( n )
We will be touching the whole tree in the search, there are n nodes in the tree and we do O(1) work at each node. There are not exactly n calls though but I need to double check this...I need to solve the recurrence but oh well...we know it will stay linear in the asymptotic regard.
Space: O( h )
Stack usage at maximum will be the trees height. Worst case would be O(n) if our tree is skewed purely to the left or right and we need to find deep nodes. But n IS h in that case. But we say O( n ) in that case since it is more accurate to what is happening, the tree's size in nodes dominating the height.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech - Věda a technologie
![LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON]](http://i.ytimg.com/vi/vZxxksAP8yk/mqdefault.jpg)
Table of Contents:
The Problem Introduction 0:00 - 0:33
Getting Good At Tree/Recursive Problems 0:49 - 2:51
What We Will Learn In This Video 2:51 - 3:34
Case #1: The Common Case 3:34 - 5:27
Case #2: The Overlap Case 5:27 - 6:47
The Key To Recursion. Reduction To A Single Focus. 6:47 - 7:55
Defining Our Recursive "Policy" At A Single Node 7:55 - 9:15
Policy #1: Both Found 9:15 - 9:32
Policy #2: Either Found (but not both) 10:48 - 12:51
Live Code Run-through 12:51 - 16:05
Time Complexity 16:05 - 17:15
Space Complexity 17:15 - 18:50
Wrap Up 18:50 - 20:10
Mistakes:
9:34 -> I meant "if we find x on the right", not "if we find x on the left"
16:35 -> We don't have a "potential" to touch the whole tree, we will touch the whole tree with this approach. Even if the LCA is found in say...the left subtree of a node...it will still make an LCA call to its right and of course get 'null' back since both nodes were already found in the left subtree and an LCA was already reaped.
Before You Say It:
For the 2nd base case we do value comparisons and this can present a problem if the value at a node we are searching for is repeated in the tree. This can simply be converted into a reference check since in the problem (at the time this video was made) passes us the reference to the 2 nodes we are searching for an LCA for. References in memory will always be unique per node.
The code for this approach to the LCA problem as applied to Binary Trees is in the description. Fully commented for teaching purposes.
Hi man, where is the code? It's not in the description.
You make me feel normal. That's a compliment. All week I've been feeling like I'm never gonna get it.
You are normal. These problems just suck. Stick with it. If I can do this, anyone can.
Glad I'm not the only one!
This guy is really kind
I just want to say that your videos has actually helped me immensely especially solving tree problems. Your approach of taking a tree problem and then thinking it based on one single node is priceless. A thousand thanks to you man! Today I landed my dream job!
Anyone who is reading this, do watch all his videos, they are awesome.
Oh nice!!! Glad you are happy. Wish you the best - your internet friend Ben
Before one understands Recursion, one must first understand Recursion!
I know, that's a joke, but it hurts.... Very bad.. Very deep!
ye
Your joke overflows.. :P
Improved version:=> Before one understands recursion one must first understand recursion until he or she understands recursion :)
Sorry but maximum recursion limit has been reached .
This was a great explanation.
I have been watching all your videos, a couple of them every day, coding them out later, and trying to make myself good enough for constructing a logical thinking for these interview questions.
No tutor on internet teaches via giving the intuitive approach, and that is what sets you apart, and makes you stand out!
You really do a wonderful job! Thanks a lot!
great good luck
Keep it up, been watching you for over a month and already feel like i've learned so much!
nice
Damn, this is THE VIDEO to watch when you're starting out with Recursion and Trees. You're awesome man!
ye
it looks like you have spend a lot of time going deep into the concepts to make these type of problems easy for us. Thanks for such hard work. Hope your content gets more views.
thanks for watching
Thank you! I solved this initially using two stacks, but the runtime was pretty abysmal. This makes the optimal solution much more clear!
nice
you gave me a chance to make myself better than yesterday...
I really liked that you include the code and walk us through it in this video. Thank you for sharing!
sure
The way you explain concepts is exceptional! Keep up the great work!
thanks
Thanks for this video man, getting me to try and understand recursion a little better at least
nice
This is the best video on recursion I have watched. Still not able to fully apply recursion to other problems but this makes a lot of sense how to "read" the function when the results from bottom come up and hit base.
Nice and it just takes time.
This is the best video about trees I have ever seen. Thank you so much!
The way you explained each and every thing related to a problem is just amazing
thanks
Those few words of the beginning. Thank you man, I'm still struggling with most of the problems I encounter. I thought I was stupid or something.
hola bro wassup
Great Explanation :) Appreciate your hard work !!!
sure
There is no chance that I would be able to think this out in an interview by myself. Anyways, thanks for the lucid explanation.
yeah, me neither
Thanks a lot.
Working on my recursion.
nice
thank you so much!! I finally understood this after watching your video. I was struggling to understand this before watching your video.
great
Best explanation and great advices not from senior-shmenior, but for usual human and in human language. Thanks!
sure
Please keep making such videos more. It's really helpful.
This is the best explanation I have found for this problem in the internet. Thank you
you will be a big reason why i get a job at the big boys in six months if i make it. bro this content is so gooooold cause you actually break it down. i don't even need to see the code cause the concepts are so good dam
great - live a good life
love the whiteboard approach (for interviewing), thanks so much!
sure
Excellent explanation regarding the recursive call!
thx
I finally understood the key behind solving recursive problems. Thank you!
nice.
You're the best explaining. It's amazing.
no u
He helps you to deeply understand the problem deeply. Very grateful to break up study sessions with his lectures.
This videos is really helping to understand how this LCA works. The basic idea is first to find out is where are those two nodes are and second do the return and determining whether is common ancestor
Thank you so much for sharing. Is that possible we can see you solve LCA similar questions on Leetcode and compare what difference between all to them?
This way of showing and explaining code is really great👍
great
Your explanations are very good. Thanks! Preparing for Amazon On Site Interview from here.
nice, good luck
Am very scared looking at problem on trees and graphs but your explanation is making me understand them easily . thank you for all the videos on trees
Give it time, they get easy
Best video. Thanks a lot!
Great explanation, some important things that I think are worth mentioning here.
I think the implementation is actually a bit wrong. For example for the below binary tree, lets say we want to find out the LCA of nodes 5 and 6. With the implementation shown in this video, the left recursive call will satisfy the base case at node 5, because node 5's value matches, so it will return the Node 5 without trying to find the match for Node 6 in the left subtree.
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
So to really start the evaluation from bottom of the tree to top, the recursive calls should be done first, before checking the Node's value.
Below is the implementation :
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return null;
TreeNode leftSearchResult = lowestCommonAncestor(root.left, p, q);
TreeNode rightSearchResult = lowestCommonAncestor(root.right, p, q);
if (root.val == p.val || root.val == q.val)
return root;
if(leftSearchResult != null && rightSearchResult!= null )
return root;
return leftSearchResult != null? leftSearchResult : rightSearchResult;
}
}
The leetcode question guarantees that both nodes p and q will always exist in the binary tree.
But If only one node exist in the tree then above implementation will return the node that matched the value in the binary tree. Which is kind of wrong, ideally it should have returned null because we were not able to find both the nodes in the tree.
=============== Follow up question =========
What if we are not guaranteed that both nodes p and q will exist in the binary tree?
Approach :
We are going to take two boolean properties firstNodeExist and secondNodeExist, and when we find that first or the second node exist in the binary tree, we will set the appropriate boolean property to true. This way we can find out whether both the values exist in the tree or not, and if both the values are not found in the binary tree we return null as LCA from the lowestCommonAncestor method.
Implementation :
class Solution {
public boolean firstNodeExist;
public boolean secondNodeExist;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return null;
TreeNode lca = lca(root, p, q);
return (firstNodeExist && secondNodeExist)? lca : null;
}
public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return null;
TreeNode leftSearchResult = lca(root.left, p, q);
TreeNode rightSearchResult = lca(root.right, p, q);
if (root.val == p.val) {
firstNodeExist = true;
return root;
} else if(root.val == q.val) {
secondNodeExist = true;
return root;
}
if(leftSearchResult != null && rightSearchResult!= null )
return root;
return leftSearchResult != null? leftSearchResult : rightSearchResult;
}
}
I made some notes here github.com/eMahtab/lowest-common-ancestor-of-a-binary-tree , you might find it helpful.
thx
Thanks a lot for these detailed videos. How about the approach where you walk up the tree until you hit the root, for both nodes and create two arrays containing parents of the nodes.
Then we can run a loop and keep on matching the parents from both these arrays and return when we’ve found a difference. That would represent the lowest common ancestor in my opinion.
Yes. I'm familiar with this approach. We would need parent pointers for that.
Great explanation! Thank you. Best of luck with your internship.
thanks
Loved the thinking behind it
Thank you for your great explanation. Awesome that you mentioned about focusing on a node. Imho, it is a bit clearer with languages that support sum types and pattern matching as you simply list all possible variants. However, I believe, the key question is still open. Why did you do `if (leftSearchRes == null) return rightSearchRes; if (rightSearchRes == null) return leftSearchRes;`. Everything else makes sense, but this is a key twist to the whole problem, I assume.
If both are null then the latter if statement still returns null for the search. Otherwise, it is a matter of passing up the result from a single successful subtree search.
This is the best video on trees and recursion! on my way to solve all Tree questions on LC -->
Great explanation. Thanks a ton man!
Dude, You just made it so easy.
Saw you're linkedin. Can't believe you doing so much only when you're 21.
I'm 20 rn and nah, it is nothing. Anyone can do anything whenever (within biological, physics, & genetic constraints).
extremely helpful!!!
Great explanation!
Thank you so much 🧡
干的漂亮！
Great explanation! Thank you!
sure
Thank you soooo much for the video, You explanation is really clear and intuitive :) If you looking for next subject for a video, can you do minimax? Me and my friend have a hard time to understand the minimax u.u
maybe, I only take requests of Patrons for now to be fair to those supporting the project
great explanation! keep up the good work
thx
You are really great!
Finalllllly .. a good video .. after searching recursively for 2 hrs.. 😁😁
nice
Thanks for the great video. I think there is a typo in function names. The initial name is "lca", however in recursive calls, "search" function is called. One of them should be changed to match the other one.
Again awesome job and good luck!
yeah noted, thanks
You make it sooo easy.
The best teacher out there :D
wow you're an excellent teacher!
Great explanation. I really admire your videos. Got a question though.
This algorithm assumes both the nodes we are finding exist in the tree somewhere. How would the algorithm change if we are not sure whether both of those exist in the tree?
I'm not sure, would have to think on this.
Great explaination !!
thanks
Very good explanation
love it !!!!!!!!! Great Expl..
thx
Elegant Explanation
thx
Amazing explanation:)
Thank u buddy☺️ u r amazing
You're Goated!
thanks!!
Can u please tell why we return the left root if right is not having any node or we return right node if left is not having any node?
12:25
Thank you!
sure
Hey this algorithm will only work for non duplicates values of the nodes whose LCA is to be find out? am i correct? wht i mean is lets suppose i am finding LCA for 5, 2. And i find multiple occurrences of 5 and 2, then this algo wont work right?
Great job!
ye
Who are you, who are you so wise, in the ways of Computer Science?
Well, memes apart, your explanation was really on point and easily understandable for a non-pro coder like me. I also get confuse and scared of recursion and tree problems. Thank you!
All the best and stay safe!
thx and thx
Awesome, thank u for rich content
Sure
Great explanation & cool algo.
There's a minor bug:
If only one of the values (x or y) is present in the tree, instead of returning NULL, it returns the Node that contains the value x or y as the LCA.
The problem assumes both nodes are present
Hey Nice explanation :). Could you make a video on Tries data structure and Segment Tree. Thanks :)
I may but I only now take video suggestions from Patrons to be fair to the people monetarily supporting the project
Hey Benyam! Thanks a lot for this great explanation. I had some doubts regarding LCA but its all gone now. I just noticed a little typo in the pseudocode that you showed (the function name is lca() but you call search() for the leftSearchResult and rightSearchResult). Apart from that the video and the explanation were super easy to understand! Thank a lot!
I would look into this but too busy. Just want you to know I saw this and can't respond
@@BackToBackSWE Well it's just a small typo. Moreover you already have the correct code in GitHub.
@@arnabbiswas2773 ok
Thank you so much
sure
love your videos bro!
thx
Hi there! is the code still in the description?
Very clear, Nice job! Why there are so many guys on CZcams can teach better than college professors...
Hahaha, maybe we are college professors in disguise 👀👀🕵🕵
But in all seriousness, a student is better positioned to teach concepts to other students than a seasoned professor is because a student knows exactly how other students will get stuck.
Aka...most esteemed professors do research and are very, very, brilliant. Much more than any outsider could comprehend.
But...there is a coefficient of loss that teaching introduces to that intellect. A perfect lesson builds a perfect bridge from the student's current level of understanding, to the teacher's understanding.
So for me...I'm not that smart, I'm not the best problem solver...but I can angle lessons in a way that will bring anyone into my mind and way of thinking better because I had to cross that bridge only 1 or 2 years ago.
Many professors and teachers crossed their bridge 10's of years ago and they lose that connection to the student's plight.
Long story short...teaching is a whole different skill and a hard one to get right.
Regardless, I have the utmost respect for all those who have every taught me (both terrible and brilliant). It is the nature of things that make it this way.
Very very very very hard to get right.
Afterward: Dang...this is a wise comment I think...something I'd read on Reddit in retrospect.
@@BackToBackSWE Agreed, that make sense. Anyways, I was confused about LRU cache implementation and LCA for a long time but fortunately I saw your video in my recommendation list today and I can now finally understand them...Thank you for your hard work and keep going!!
@@sui8261 Will do
Helped a lot, can you do some oo design questions?
yeah
quick question, would we not return lca(root.right) and lca(root.left) as the function given isnt recursive
Will this still work if one of the nodes that we are looking for is not present in the tree?
Awesome!!!!
thanks
Genius!!!!
Could you explain how can we do it for a graph or a n-ary tree. Thanks
yes
I encountered this problem for the first time in an interview for one of the Big Four. My dumb ass maintained an array of the references of the parents of each node to be found and compared the references to find a common point. No wonder they kicked me out. :(. Thanks to Ben, I will get MY REVENGE.
hahahahaha
Why is this a terrible solution? The time complexity is the same because each node is visited at most twice. The space complexity is O(n) instead of O(h) which is much worse for a balanced tree. But it's still a reasonable solution, right?
@@SunkuSai I agree, but I believe the other interviewees came up with this solution, and the interviewers had a limit or something.
@@SunkuSai can you explain more about your approach 🙏 which array you are talking about
@@notyournormaldev1419 search for x , and store its path in an array. Do the same for y. Now start comparing those arrays, when you encounter different values at an index, the index before that stores the LCA.
thanks man! you are awesome
thx
great explenation where is the code ?
I think the beginning talk is more precious than how to solve this problem.
You’re the best
no u
Where is the code(link) in description? Kindly let me know. Please provide the link.
Thank you.
The repository is deprecated - we only maintain backtobackswe.com now
the recursive functions dont match the function names (lca vs search) a bit confusing but still got the gist of it
With the function search(root, x, y) you are referring to lca(root, x, y), right?
yeah, it is just a name change. You are basically searching for occurrences of either x's val or y's val and bubbling up the appropriate result.
Great! Thanks for getting back so quickly. Keep up the great videos like this one and I'm sure you will reach your goal before you know! Cheers :-) @@BackToBackSWE
@@Quintenkonijn cheers
had this on an exam recently lol thx
nice
Same for an interview. But worded different so realizing it's a lca is a major key.
Another easier to understand algorithm is:
1. find both nodes while counting the depth for each
2. if one of the nodes is deeper than the other, bring that variable up to reach the same depth as the other
3. now both are on the same depth. Bring both of them up 1 node at a time until they point to the same node.
This requires node to have a pointer to its parent though
Great Explanation! Just had a doubt, shouldn't the search be the same recursive function? That is, search(root.left,x,y) should be a recursive call to lca(root.left,x,y)
I don't remember the code presented in this video.
Hi have an edge case senario how will you handle it can anyone please explain it to me based on the above algo the base case is failing
Root node is ‘a’ its right child ‘c’ its right child is ‘h’.
A
*
C
*
H
If you search for lca of C and I ( where I is not part of graph )
The above algo returns C where as i think it should return null as there is no common ancestor
Please help
How do handle case where X and Y are not present in the tree
If both are not present then null will be returned, this is already handled. The null base case would be the only one hit and all results coming back up the tree would be null thus returning null at the top call
Will your solution work on this tree? Because I don't think it will. It will return 4 instead of null?
Lca(3, 4, 5)
3
\
4
\
6
I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.
really clean solution code
ye
@@BackToBackSWE Seriously, I have need researching various ways to solve LCA, this is by far the most elegant code. I noticed some of your solutions are from EPI, but EPI has a different recursive solution for this and the one you explain I love a lot more. Thanks!
@@TheDEMMX great