Medium Recursive Descent Advanced Trees
In plain English: Find the deepest node in a binary tree that is an ancestor of both given nodes.
Recurse left and right. If p and q are in different subtrees, the current node is the LCA. If both are on one side, the LCA is in that subtree.
Prompt
Given a binary tree and two nodes p and q, find their lowest common ancestor (LCA).
Try to write it from scratch before scrolling down.
Solution
def lowest_common_ancestor(root, p, q):
if root is None or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root # p and q are in different subtrees
return left if left else right
# Test: tree = [3,5,1,6,2,0,8], LCA(5,1) = 3, LCA(5,4) = 5