LOWEST COMMON ANCESTOR OF A BINARY TREE II | PYTHON | LEETCODE 1644

In this video we are solving Lowest Common Ancestor of a Binary Tree II. This is an interesting problem because it's basically a carbon copy of the first iteration of this problem except this time we are not guaranteed to have the nodes P and Q exist in the tree.

[@yashshukla1637]

Thank you so much brotha! may GOD bless you with more TC from meta!!!

[@chasing_the_horizon]

Wow, the explanation was super clear! Thx, mate!

[@crackfaang]

Thanks! Make sure to subscribe if you haven’t already 😉

[@symbol767]

Within in the first 3 minutes of your video I figured out why my code wasn't working. Once I did a check for P and for Q separately first to confirm they both exist, my solution started working.
All I had to do is check if P or Q doesn't exist and return Null, if they both exist, then I can do the normal "find ancestor" code.
But of course this wasn't efficient enough, so thank you for showing me the optimized version

[@FluteVJ]

Thank you . Your channel videos are super easy to understand.

[@hangchen]

8:59 sorry I am confused here. If returning 4 or 5 doesn't matter, how would the algorithm make sure to return the correct answer, 5 but not 4?

[@klppdc]

Yes. This is the same question I have. Also if P and Q both are found in left subtree, why do we have to still traverse right subtree? That does not seem necessary.

[@jaisoni1]

Great Explanation! Thanks!

[@crackfaang]

Glad you enjoyed the video! Make sure to subscribe so you don’t miss future videos

[@yashshukla1637]

how l or r works was something new to me
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
self.p_found = False
self.q_found = False
ans = self.helper(root, p, q)
return ans if self.p_found and self.q_found else None
def helper(self, node, p, q):
if not node:
return None
l = self.helper(node.left, p, q)
r = self.helper(node.right, p, q)
if node == p:
self.p_found = True
return node
if node == q:
self.q_found = True
return node
if l and r:
return node
else:
return l or r

[@jimmyahmed5424]

Thank you for explaining, it was helpful!

[@crackfaang]

Glad you found the video helpful! Make sure to subscribe so you don’t miss other videos coming soon

[@davidc4322]

Wouldn't storing l and r result in an O(N) space complexity? Since the None value also takes space in memory as well.