Recursion

Lowest Common Ancestor in a BST

Given a balanced BST root and two values in the tree p and q, return the value of their lowest common ancestor. To make the problem simpler, all the values in the tree are unique.

Example:

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

Hint: Finding the LCA of a regular tree is $O(n)$ . Can you use any information about BSTs to make a faster algorithm?

First Few Test Cases:

0. Problem

We want to find the LCA of the tree, given the values of the two nodes.

1. Recursion

We want to somehow include a Binary Search in our algorithm so that it runs quickly.

Let's use an example:

How can we use a binary search to find the answer? If we did a binary search for p, we would start out at the root node and move left. And if we did a binary search for q, we would also move left.

The idea is to keep following the binary search on p and q, until we get to a node where the binary search for the two nodes disagrees. For example, in the above image, when you're at the LCA, the binary search for p tells you to move left, and the binary search for q tells you to move right, so they disagree with each other.

Here's the recursion for this:

2. Base case

The recursion automatically stops when we hit the LCA, so there's not really a base case here.

3. Code

Since there's no base case, the code is just the recursion above. We'll write it again for clarity:

Time Complexity $O(n)$ . This is really the height of our tree, which is O(n) since we're not necessarily given balanced BSTs.

Space Complexity $O(n)$ for the Call Stack. Again, this is really the height of our tree.

This is very easy to make iterative - see below.

Mark as Completed:

Submits:

LCA

Imports:

TreeNode

Test your code to get an output here!

LCA(

)

Test your code to get an output here!