LeetCode 235 · Trees

Lowest Common Ancestor of a Binary Search Tree, explained with a picture

Where two relatives’ family lines split.

MediumTrees
▶ Watch it step by step

The problem

In a binary search tree (smaller values on the left, bigger on the right), find the lowest common ancestor of two nodes p and q: the deepest node that has both of them below it (a node counts as below itself).

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

Picture it

Picture a family tree where you’re looking for where two relatives’ family lines split. Start at the top. If both p and q are smaller than the current person, both live on the left side, so go left. If both are bigger, go right. As soon as they fall on different sides (or one of them is the current person), this is where their lines split.

How to recognise it

  • The tree is a binary search tree (BST): smaller values on the left, bigger on the right, at every node.
  • The question is about where two values' paths from the root split: the lowest node with both values below it (a node counts as below itself).
  • In a BST, comparing a value with a node tells you which side it is on, without searching. That means you can walk down one path.
  • Up to 10^5 nodes, so avoid visiting them all when the order already points the way.

Start with brute force

Ignore the ordering and use the general method for any binary tree: search both subtrees, and the node where p and q come back from different sides is the answer.

def lca_general(root, p, q):          # ignores the BST order
    if not root or root.val in (p, q):
        return root
    left = lca_general(root.left, p, q)
    right = lca_general(root.right, p, q)
    if left and right:
        return root
    return left or right

It is correct, but it may visit every node: O(n) time, about 10^5 steps here, and O(h) recursion space, where h is the height. A chain of 10^5 nodes would also overflow Python's default recursion limit of about 1,000 frames.

From brute force to the idea

  1. Find the waste. The general method searches both sides because it cannot know where p and q are. In a BST it can.
  2. Compare with the current node. If both values are smaller than node.val, both are in the left subtree, so their lowest common ancestor is too: go left. If both are bigger, go right.
  3. Recognise the split. Otherwise, one is on each side, or one of them equals node.val. In both cases no deeper node has both below it, so this node is the answer.
  4. No recursion needed. Each step moves one level down, so a simple while loop does it.

This is the key idea: walk down from the root while both values lie on the same side; the first node where they do not is the lowest common ancestor.

The shown code takes p and q as values. On LeetCode they are nodes, so compare p.val and q.val instead.

The key idea

Use the BST ordering: walk down while p and q are on the same side. O(height).

Python solution

def lca(root, p, q):
    node = root
    while node:
        if p < node.val and q < node.val:
            node = node.left          # both are smaller: go left
        elif p > node.val and q > node.val:
            node = node.right         # both are bigger: go right
        else:
            return node               # they split here

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (general tree method)O(n): may visit every nodeO(h): recursion stack
BST walk (shown code)O(h): one step per level, about 17 for a balanced tree of 10^5 nodes, up to n for a chainO(1): a single pointer

Edge cases

  • One value is an ancestor of the other (p = 2, q = 4 in [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]): returns 2, because at node 2 p equals the node value.
  • p and q in either order: (3, 5) and (5, 3) both return 4; the conditions are symmetric.
  • p equals q: returns that node.
  • A value not in the tree: the code does not check. lca(tree, 3, 100) returns 6, a node that only marks where the search paths split. LeetCode guarantees both exist.
  • Both values missing on the same side (say −5 and −1): the walk falls off the tree and returns None.
  • Very deep tree: the loop has no recursion, so a 10^5-node chain is fine.

Common mistakes

  • Using <= or >= in the "go left" or "go right" test, which walks past the node when it equals p or q.
  • Forgetting that the tree is a BST and solving the general problem: correct, but it misses the point and costs O(n).
  • Comparing node objects with numbers when LeetCode passes nodes: use p.val.
Your turn: distance between two values

In the same BST, return the number of edges on the path between the nodes holding p and q (both exist). For p = 0, q = 9 in [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] the answer is 4. Describe your approach, then write it if you like.

Compare with our answer

The path goes up from p to the split node and down to q. So find the split with the same walk, then count the steps from the split down to each value, again steering by comparison.

def distance(root, p, q):
    split = lca(root, p, q)
    def down(node, target):
        steps = 0
        while node.val != target:
            node = node.left if target < node.val else node.right
            steps += 1
        return steps
    return down(split, p) + down(split, q)

Time O(h), space O(1). When p equals q the answer is 0.

A strong answer mentions: that the path must pass through the lowest common ancestor, counting edges (not nodes) on each side, and that both searches use the BST order.

Check what stuck

1. A sorted file-system index is stored as a BST of paths. You need the deepest entry under which two given paths both fall. Which approach fits best?

2. Why does the shown solution use O(1) extra space?

3. A learner writes if p <= node.val and q <= node.val: in the first test. Which query in [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] is now wrong?

Score 60% or more and the lesson is marked complete.