The machine must find the deepest node that is an ancestor of both p and q. The LCA is the node where the paths from root to p and root to q first converge, and it is allowed to be p or q themselves when one is an ancestor of the other.
The key insight is that no path-finding is needed: a single post-order DFS can detect the LCA. Each recursive call returns whether its subtree contains p, q, or both. The first node whose subtree reports both p and q is the LCA — unless the current node itself equals p or q, in which case that node is the LCA if the other is found anywhere in its subtree.
The approach has three steps. First, recurse into both children and collect whether each one found p or q. Second, check whether the current node itself is p or q, or whether one match came from each side, or whether one side returned the LCA directly. Third, return the match result upward: the LCA once found, or a flag indicating which target was found. Each node is visited once, so time is O(n) and space is O(h) for the call stack.
The trickiest edge case is when p is an ancestor of q. The machine must return p even though the left branch alone contains everything — this is why the "current node is a target" check runs before combining child results.
def lowestCommonAncestor(root, p, q):
if not root or root is p or root is q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or right