The lowest common ancestor (LCA) of two nodes is the deepest node that has both as descendants. A node can be a descendant of itself.
For nodes and , three cases exist:
Both in left subtree → LCA is in left
Both in right subtree → LCA is in right
One in each, or current node is or → current node is LCA
The recursive approach:
def lowestCommonAncestor(root, p, q):
if root == null or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left if left else right
If both subtrees return non-null, current node is the LCA. Otherwise, return whichever subtree found something.