Lowest Common Ancestor of a Binary Tree

Problem

Given the root of a binary tree and two distinct nodes p and q that both appear in it, return their lowest common ancestor: the deepest node whose subtree contains both p and q. A node is considered an ancestor of itself, so if one of the two nodes is above the other, the upper node is the answer.

• The tree has between 2 and 150,000 nodes; it is not ordered in any way.
• All node values are distinct.
• p and q are nodes in the tree and p != q.

Examples

• root = [40, 22, 61, 8, 35, 50, 93, None, None, 30, 37], p = 22, q = 61 → 40. The two nodes are in different subtrees of the root.
• Same tree, p = 22, q = 37 → 22. 37 lives under 22, so 22 is its own ancestor and the lowest common one.
• root = [5, 9], p = 5, q = 9 → 5.

Hints

1. Walking down from the root, where do the paths to p and to q diverge?
2. If a subtree contains neither target it can report "nothing"; if it contains exactly one it can report which; what does a node conclude when its two children report different targets?
3. Post-order DFS that returns p, q, or None from each subtree; the first node whose left and right both return non-null is the LCA, and it is passed up unchanged.