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

[@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!

[@LeeK301]

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

[@crackfaang]

Yea it's definitely a cool little trick. Glad you found the video useful and learned something new. Keep up the grind 💪

[@gothfrog69]

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

[@syafzal273]

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.

[@retrofacade9832]

agree

[@rachelwilliams8569]

Thanks for the comment. I was going to mention the same thing.

[@iswariyar9169]

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

[@shelllu6888]

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!

[@cloud15487]

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.

[@vamsikrishnagannamaneni912]

yea as he didnt create a separate helper function , that condition is needed

[@aleetsai8636]

The way you explain the question is so amazing. It's really easy to understand. Thank you so 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

[@bhaveshsrivastava2112]

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

[@crackfaang]

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 😉

[@ebenezeracquah478]

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

[@jeongtaebang3679]

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?

[@fadsa342]

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

[@crackfaang]

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.

[@jimmyahmed5424]

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

[@awa8766]

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.

[@chowdhurylinianazmi5615]

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

[@awa8766]

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

[@АхтемВейс]

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.

[@leetcoderafeeq2641]

Line 19

[@vamsikrishnagannamaneni912]

it would return the parent node that recieved 6 from left and 4 from right. Directions are implied as left is returned before right.

[@mathsky4401]

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

[@crackfaang]

Haha people haven’t caught on to the channel yet. There’s a lot of Leetcode channels on KZbin

[@joebaldwin9005]

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?

[@crackfaang]

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

[@no3lcodes]

@@crackfaang You're right, they are guaranteed to be in the tree and for both of them to be different.

[@mitramir5182]

Thank you so much for the amazing explanation!

[@crackfaang]

No problem, glad you enjoyed the video!

[@PowerOfTens8420]

That was a really great explanation! Thanks

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

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

[@mdasifshahjalal3595]

Thanks for clearing this puzzle :)

[@crackfaang]

No problem, glad you enjoyed the video

[@shuier525]

You are a magic

[@subee128]

Thanks

[@cicis3621]

genius thank you

[@khaledgewily8824]

Thank you :)

[@hangchen]

I am the 100th liker! Thank you!

[@vedansh9004]

Goddamn

[@lukaszm9234]

I hate this "interview mentality", where "it doesn't hurt" to check if something is null, even when we're guaranteed that it won't be null. If I saw that in a PR I'd immediately point it out. Useless code should be deleted, not kept "just in case". Companies will hire the "Leetcode specialists" and the codebase will suffer. Please do better.