LOWEST COMMON ANCESTOR OF A BINARY TREE I | PYTHON | LEETCODE 236
Вставка
- Опубліковано 24 сер 2024
- In this video we are solving the first in the line up of lowest common ancestor problems on Leetcode: LCA of Binary Tree I. This is by far the easiest LCA problem of the bunch and lays the foundation for the rest of the problems in this series.
Links to the other videos:
LCA Binary Tree II: • LOWEST COMMON ANCESTOR...
LCA Binary Tree III: • LOWEST COMMON ANCESTOR...
LCA Binary Tree IV: • LOWEST COMMON ANCESTOR...
![LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON]](/img/n.gif)
You mentioned that you may not need the base case because we are guaranteed to have an LCA, but the base case is needed because its a recursive function and when we reach a left/right which is None, we need the base case to kick in.
agree
Thank you for making this problem make sense. Wow.... Much simpler than leetcode's "official" solution.
I like when you quickly show the use case while coding, it helps solidify what case we're on and removes the need for us to rewind quickly. And tbh rarely do ppl ever figure out the approach then go straight to coding without ever looking back at their drawing / plan. Keep up the great work!
just a Thank you is really not sufficient for this crystal clear explanation. Beyond Awesome
This is really clever thinking with the part of "return l or r". I say this because I was approaching this problem w/ the mindset that we MUST find both nodes; but I see through your example that if we find one, and we cant find the other, we just assume that the node that was found is the LCA for both! Very nice...
Yea it's definitely a cool little trick. Glad you found the video useful and learned something new. Keep up the grind 💪
the reason you're adding the base case is not to convince the interview that the tree could be null, it's needed in any case if the node we're looking for isn't in the subtree. so it's not optional at all, the base case (if root == null return root) is required.
yea as he didnt create a separate helper function , that condition is needed
The way you explain the question is so amazing. It's really easy to understand. Thank you so much!
Thank you! For the first time, I finally understood your explanation and able to code it out without looking at the solution for this problem!
space complexity should be o(h) where h is height of the tree since the call stack will hold at most h stack frames in recursive depth first search
I do like your explanations, they are intuitive and clear. Thank you very much.
Thank you so much for the amazing explanation!
No problem, glad you enjoyed the video!
That was a really great explanation! Thanks
big thanks for your video. good explanation. keep going.
genius thank you
You are a magic
Thanks
Thank you :)
Thanks for clearing this puzzle :)
No problem, glad you enjoyed the video
Beautifully explained. simplified solution and clear explanation. But why so low views?
Haha people haven’t caught on to the channel yet. There’s a lot of Leetcode channels on UA-cam
Hi, Thanks for explanation! Can you tell whats the difference between this and #1650 of leetcode.
The inputs are different. In #1650 you are only given the nodes P and Q but not root. Also, in #1650 you are given the parent pointer of each node. So in this question you go from the root down, but in #1650 you go from the nodes P and Q up instead.
I have a video on #1650 out as well. Make sure to watch that one 😉
Any advice for coming up with base cases? I looked at this problem for a while and didn't come up with there only being three possibilities
The 3 cases are not really the bases cases, they're the main meat of the problem. A base case would be handling a NULL root or something similar. It mostly comes from experience and having seen many similar problems. Nothing wrong with not being able to see it from the first try. If you are able to have an "ah-ha" moment once you see the solution then you will likely remember it forever.
Thank you for explaining! but why do we need line 13 and 14?
You need these two lines in the case p or q are your root node. If they are your root node then it's your LCA instantly because it's your tree's very first level that's common to every other node.
@@awa8766 I don’t think it’s very first level. It’s a recursive call, so you may get a match of this at any level. The intent of that line is once a node found is equal to p (or q) we won’t go further down of that node in recursion. The other parts of the tree might have q. If not the very last condition makes this node as the LCA.
@@chowdhurylinianazmi5615 You are correct and your description is more accurate. When I explained it, I saw it from a level-order perspective, but the idea is the same. The first instance of a p or a q at a root instantly guarantees an LCA.
I have one question, what if p is at the bottom of the left subtree and q doesnt exist in the tree. This would return p which is technically not the common ancestor?
You should check the constraints listed in the question itself as I don’t recall off the top of my head but I’m pretty sure for this one both p and q are required to exist in the tree
@@crackfaang You're right, they are guaranteed to be in the tree and for both of them to be different.
But what if your dfs returned 6 to you as one of the nodes and the other let’s say would be 4. You would return 6 in that case which is incorrect.
Line 19
it would return the parent node that recieved 6 from left and 4 from right. Directions are implied as left is returned before right.
I am the 100th liker! Thank you!
Goddamn