Algorithm - Recursive LCA

The recursive LCA works by searching both subtrees and combining results. Call lowestCommonAncestor on the left child and the right child. If both return a non-null node, the current node is the LCA because p and q are in different subtrees. If only one returns non-null, pass that result upward.

This is a post-order traversal. You process children before deciding about the current node. The algorithm visits each node once, giving $O(n)$ time. Space is $O(h)$ for the recursion stack, where $h$ is the tree height. For a balanced tree, $h = O(\log n)$. For a skewed tree, $h = O(n)$.