Lowest Common Ancestor of a Binary Tree

The problem. Given a binary tree and two of its nodes p and q, find their lowest common ancestor (LCA): the deepest node that has both p and q in its subtree. A node counts as an ancestor of itself.

Example

root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]
p = 5, q = 1  ->  3
p = 5, q = 4  ->  5
p = 7, q = 6  ->  5

Picture walking up from p and from q toward the root: the LCA is the first node where the two routes meet. Equivalently, walking down from the root, it's the last node whose subtree still contains both — the point where p and q split onto different sides (or where one of them is the node itself).