LOWEST COMMON ANCESTOR OF A BINARY TREE I | PYTHON | LEETCODE 236

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:

[gothfrog]

Thank you for making this problem make sense. Wow.... Much simpler than leetcode's "official" solution.

[syafzal]

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.

[LeeK]

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...

[iswariyar]

just a Thank you is really not sufficient for this crystal clear explanation. Beyond Awesome

[def__init]

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!

[aleetsai]

The way you explain the question is so amazing. It's really easy to understand. Thank you so much!

[cloud]

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.

[shelllu]

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!

[ebenezeracquah]

I do like your explanations, they are intuitive and clear. Thank you very much.

[energy-tunes]

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

[PowerOfTens]

That was a really great explanation! Thanks

[mitramir]

Thank you so much for the amazing explanation!

[jeongtaebang]

Technically, this algorithm can also handle the case where both nodes are not present in the tree right? It just cannot handle the case where only one node is present in the tree?

[bhaveshsrivastava]

Hi, Thanks for explanation! Can you tell whats the difference between this and #1650 of leetcode.

[ВладСкригун]

big thanks for your video. good explanation. keep going.

[fadsa]

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

[mathsky]

Beautifully explained. simplified solution and clear explanation. But why so low views?

[АхтемВейс]

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.

[joebaldwin]

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?

[jimmyahmed]

Thank you for explaining! but why do we need line 13 and 14?