Recursion

Given the root node of a binary tree `root`

and two values in the tree `p`

and `q`

, return the value of their lowest common ancestor. All the values in the tree are unique.

**Example:**

$\notag
\begin{align*}
&\large \texttt{p = 6} \\
&\large \texttt{q = 15} \\[8bp]
&\large \texttt{=> returns 3}
\end{align*}$

First Few Test Cases:

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$.

Mark as Completed: