0. Problem

The LCA is the node where p is to the left and q is to the right, or vice versa:

The LCA can also equal p and have q in one of its subtrees, or vice versa:

Putting these together, here's the equation for the LCA. The function hasPorQ computes whether p or q shows up in a subtree.

1. Recursion

It's not obvious how to find a recursion for LCA, but we definitely need to compute hasPorQ at each node in the tree, so we might as well find a recursion for that. Here's the recursion for hasPorQ:

Notice that this recursion already computes everything we need in order to compute the LCA. So a clever idea is to "hijack" it, and use it to compute the LCA. We can do this by just copying the above recursion and sticking in a line of code:

2. Base case

The base case is:

3. Code

We just have to combine the recursion and base case. We'll keep a global variable "LCA", and update it when we see a node that could be the LCA. Here's the code:

Note that hasPorQ runs on low nodes first and high nodes last, because it gets set after hasPorQ was already called on the node's children. This is important, because we need to return the highest node that satisfies this equation.

Time Complexity $O(n)$. We visit each node once and do an $O(1)$ operation on it.

Space Complexity $O(n)$. The Call Stack grows up to size $n$.