LC 0236 [M] Lowest Common Ancestor of a Binary Tree (LCA) - ALawliet/algorithms GitHub Wiki
here we are given p, q, AND x (so we can use recursion)
go bottom-up (post-order) and if we come back up with both found, by the nature of the recursion, then this must be the LCA
https://www.youtube.com/watch?v=py3R23aAPCA&t=607s&ab_channel=BackToBackSWE
(x == p or x == q) => return x
because the LCA of a node is the node itself
constraint: p and q always exist
class Solution:
def postorder(self, x, p, q):
if not x: return None
if x in [p, q]: return x
L = self.postorder(x.left, p, q)
R = self.postorder(x.right, p, q)
return x if (L and R) else (L or R)
if L and R:
return x
return L or R
class Solution:
def lowestCommonAncestor(self, x, p, q):
if not x: return None
# node is p or q so descendant of itself
if x == p or x == q:
return x
L = self.lowestCommonAncestor(x.left, p,q)
R = self.lowestCommonAncestor(x.right, p,q)
# x is the ancestor node we are checking and now has info about L and R subtree descendants
if L and R: # node has both p and q as descendants
return x
else: # only one or the other subtree has
return L or R
class Solution:
def lowestCommonAncestor(self, root, p, q):
if not root: return None
left = self.lowestCommonAncestor(root.left, p , q)
right = self.lowestCommonAncestor(root.right, p , q)
if root == p or root == q:
return root
if left and right:
return root
if not left:
return right
if not right:
return left
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def dfs(node):
# if not node.left or not node.right: pass # leaf don't matter and we know they're in the tree somewhere
# bottom-up
# if we get an L or R node back, it means that traversal found p or q, else we hit that leaf without finding one
L_had_p_or_q = R_had_p_or_q = None
if node.left:
L_had_p_or_q = dfs(node.left)
if node.right:
R_had_p_or_q = dfs(node.right)
# if looking for me, return myself - node can be LCA of itself
if node == p or node == q:
return node
# if BOTH sides returned a node, means both p and q have been found, so this current parent node must be LCA
if L_had_p_or_q and R_had_p_or_q:
return node
# if EITHER one of the children returned a node, meaning either p or q found on left or right branch
# Ex: assuming 'p' found in left child and right child returned 'None'. This means 'q' is
# somewhere below node where 'p' was found so we don't need to search the right path all the way,
# because in such scenarios, node where 'p' found is LCA
return L_had_p_or_q or R_had_p_or_q
return dfs(root)