LeetCode 235: Lowest Common Ancestor of a Binary Search Tree

Problem Restatement

We are given:

• The root of a binary search tree
• Two nodes p and q

We need to find their lowest common ancestor.

The lowest common ancestor, usually called LCA, is the lowest node in the tree such that both p and q are descendants of that node. A node may be a descendant of itself.

LeetCode examples include:

Input:
root = [6,2,8,0,4,7,9,null,null,3,5]
p = 2
q = 8

Output: 6

and:

Input:
root = [6,2,8,0,4,7,9,null,null,3,5]
p = 2
q = 4

Output: 2

The tree contains unique values, and both p and q exist in the BST. (leetcode.com)

Input and Output

Tree node shape:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Function shape:

class Solution:
    def lowestCommonAncestor(
        self,
        root: 'TreeNode',
        p: 'TreeNode',
        q: 'TreeNode'
    ) -> 'TreeNode':
        ...

Examples

Example 1:

Tree:
          6
        /   \
       2     8
      / \   / \
     0   4 7   9
        / \
       3   5

p = 2
q = 8

The answer is:

6

because:

• 2 is in the left subtree of 6
• 8 is in the right subtree of 6

So 6 is the first node where the paths split.

Example 2:

p = 2
q = 4

The answer is:

2

because:

• 2 is an ancestor of 4
• A node can be an ancestor of itself

So the lowest common ancestor is 2.

First Thought: Store Paths

One possible method is:

1. Find the path from root to p
2. Find the path from root to q
3. Compare the paths
4. The last common node is the LCA

This works for any binary tree.

But here we have a binary search tree, which gives much stronger structure.

We can solve the problem without storing paths.

Key Insight

A binary search tree satisfies:

all left subtree values  < root value
all right subtree values > root value

So the relative positions of p and q determine where the LCA must be.

There are only three possibilities.

Case 1: Both Nodes Are Smaller

Suppose:

p.val < root.val
q.val < root.val

Then both nodes are in the left subtree.

So the LCA must also be in the left subtree.

We move left.

Case 2: Both Nodes Are Larger

Suppose:

p.val > root.val
q.val > root.val

Then both nodes are in the right subtree.

So the LCA must also be in the right subtree.

We move right.

Case 3: The Nodes Split

Suppose:

p.val < root.val < q.val

or:

q.val < root.val < p.val

Then one node is on each side.

That means the current root is exactly the first point where the paths diverge.

So the current root is the LCA.

This also covers the case where one node equals the root.

Visual Example

Consider:

          6
        /   \
       2     8
      / \   / \
     0   4 7   9

Find LCA of:

2 and 8

At root 6:

2 < 6
8 > 6

The nodes split around 6.

So:

LCA = 6

Now find LCA of:

2 and 4

At root 6:

2 < 6
4 < 6

Both are left.

Move left to 2.

Now:

p = 2
q = 4
root = 2

One node equals the current root.

So:

LCA = 2

Algorithm

Start at the root.

Repeatedly:

1. If both p and q are smaller than the current node:
   • Move left
2. Else if both are larger:
   • Move right
3. Otherwise:
   • Return the current node

The loop stops as soon as the nodes split or match the current node.

Correctness

At every step, the BST ordering property guarantees that:

• All smaller values lie entirely in the left subtree
• All larger values lie entirely in the right subtree

If both p and q are smaller than the current node, then every common ancestor must lie in the left subtree. Moving left preserves the correct answer.

Similarly, if both are larger, every common ancestor must lie in the right subtree. Moving right preserves the correct answer.

Eventually, one of two things happens:

1. The nodes lie on different sides of the current node.
2. One node equals the current node.

In either case, the current node is the first node whose subtree contains both p and q.

Therefore, the current node is their lowest common ancestor.

Complexity

Here, h is the height of the tree.

For a balanced BST:

h = O(log n)

For a skewed BST:

h = O(n)

Implementation

class Solution:
    def lowestCommonAncestor(
        self,
        root: 'TreeNode',
        p: 'TreeNode',
        q: 'TreeNode'
    ) -> 'TreeNode':

        while root:
            if p.val < root.val and q.val < root.val:
                root = root.left

            elif p.val > root.val and q.val > root.val:
                root = root.right

            else:
                return root

Code Explanation

We start at the root:

while root:

If both target values are smaller:

if p.val < root.val and q.val < root.val:
    root = root.left

then both nodes must be in the left subtree.

If both target values are larger:

elif p.val > root.val and q.val > root.val:
    root = root.right

then both nodes must be in the right subtree.

Otherwise:

return root

This means:

• the nodes split across the current node, or
• one node equals the current node

In both situations, the current node is the lowest common ancestor.

Recursive Version

The same logic can be written recursively.

class Solution:
    def lowestCommonAncestor(
        self,
        root: 'TreeNode',
        p: 'TreeNode',
        q: 'TreeNode'
    ) -> 'TreeNode':

        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)

        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)

        return root

The iterative version avoids recursion stack usage, so it uses constant extra space.

Testing

from collections import deque

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def build_tree(values):
    if not values:
        return None

    root = TreeNode(values[0])
    q = deque([root])
    i = 1

    while q and i < len(values):
        node = q.popleft()

        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            q.append(node.left)
        i += 1

        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            q.append(node.right)
        i += 1

    return root

def find_node(root, value):
    if root is None:
        return None

    if root.val == value:
        return root

    if value < root.val:
        return find_node(root.left, value)

    return find_node(root.right, value)

def run_tests():
    s = Solution()

    root = build_tree([6,2,8,0,4,7,9,None,None,3,5])

    p = find_node(root, 2)
    q = find_node(root, 8)
    assert s.lowestCommonAncestor(root, p, q).val == 6

    p = find_node(root, 2)
    q = find_node(root, 4)
    assert s.lowestCommonAncestor(root, p, q).val == 2

    p = find_node(root, 3)
    q = find_node(root, 5)
    assert s.lowestCommonAncestor(root, p, q).val == 4

    root = build_tree([2,1])
    p = find_node(root, 2)
    q = find_node(root, 1)
    assert s.lowestCommonAncestor(root, p, q).val == 2

    print("all tests passed")

run_tests()