Lowest Common Ancestor of a Binary Search Tree

The problem

root is the top node of a binary search tree. Each node has a number val and up to two children, left and right; a missing child is null. A binary search tree keeps its values in order: everything reached through a node's left child is smaller than the node's value, and everything reached through its right child is larger. All values are different. A node's ancestors are that node and every node above it on the way to the root. p and q are the values of two nodes. Return the value of the lowest node, the one farthest from the root, that is an ancestor of both.

What to write

type TreeNode = {val:number;left:TreeNode|null;right:TreeNode|null};

function solve(root: TreeNode | null, p: number, q: number): number

Input
root = {"val":6,"left":{"val":2,"left":{"val":0,"left":null,"right":null},"right":{"val":4,"left":{"val":3,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}},"right":{"val":8,"left":{"val":7,"left":null,"right":null},"right":{"val":9,"left":null,"right":null}}}
p = 2
q = 8

Output
6

Input
root = {"val":6,"left":{"val":2,"left":{"val":0,"left":null,"right":null},"right":{"val":4,"left":{"val":3,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}},"right":{"val":8,"left":{"val":7,"left":null,"right":null},"right":{"val":9,"left":null,"right":null}}}
p = 2
q = 4

Output
2

Constraints

Values are unique and both nodes exist.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   You are given two values, not nodes, and a node has no link back to its parent. So you cannot start at p or q and climb: any walk has to start at the root and go down. Both values are promised to be in the tree, so you never have to handle a missing one.

2. Hint 2: Ask a smaller question

   Stand on the root of example 2, which holds 6, with p = 2 and q = 4. Without looking at the rest of the tree, can you say which side of the root both values are on? What changes if q is 8 instead?

3. Hint 3: Name the pattern

   The signal is the ordering: comparing a value with a node tells you which side of that node the value is on. While p and q are on the same side, their lowest common ancestor is on that side too. Steering a walk by such comparisons is binary search tree ordering. Read the lesson on binary search tree ordering.

4. Hint 4: State the invariant

   The node you are standing on is always an ancestor of both values. You step to a child only when both values are on that child's side, so the child is an ancestor of both as well. When they are not on the same side, no child is.

5. Hint 5: Sketch the pseudocode

   Start at the root. Repeat: if p and q are both smaller than the node's value, move to its left child. If both are larger, move to its right child. Otherwise return the node's value.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Both targets on one side imply the ancestor lies on that side. The first split point, including either target, is the answer.

The slow way

Search the whole tree for p and write down the path from the root to it. Do the same for q. The answer is the last node the two paths share. It is correct in any binary tree, but it can visit every node, it stores two paths, and it never uses the ordering that this tree has.

The insight

Compare p and q with the node you are on. Both smaller: both are on its left side, and so is their lowest common ancestor. Both larger: the same on the right. Anything else means they part ways here, or one of them is this node, so this node is their lowest common ancestor.

Step by step

1. Walk down from the root, which is an ancestor of every node. Every node is reached from the root, so the root is a common ancestor of any two values. The walk only ever replaces it with a lower one.
2. Both values are smaller than this node: go to its left child. Smaller values are only on the left side. Both nodes are down there, so the left child is an ancestor of both, and it is lower than this node.
3. Both values are larger than this node: go to its right child. The mirror case. Larger values are only on the right side, so the right child is a lower ancestor of both.
4. Otherwise this node is the lowest common ancestor. Either the two values are on different sides, or one of them is this node. In both cases neither child is an ancestor of both, so nothing lower can be.

The same numbered steps are the comments in each solution.

function solve(root, p, q) {
  // 1. Walk down from the root, which is an ancestor of every node
  let node = root;
  while (true) {
    // 2. Both values are smaller than this node: go to its left child
    if (p < node.val && q < node.val) node = node.left;
    // 3. Both values are larger than this node: go to its right child
    else if (p > node.val && q > node.val) node = node.right;
    // 4. Otherwise this node is the lowest common ancestor
    else return node.val;
  }
}

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };
function solve(root: TreeNode | null, p: number, q: number): number {
  // 1. Walk down from the root, which is an ancestor of every node
  let node = root!;
  while (true) {
    // 2. Both values are smaller than this node: go to its left child
    if (p < node.val && q < node.val) node = node.left!;
    // 3. Both values are larger than this node: go to its right child
    else if (p > node.val && q > node.val) node = node.right!;
    // 4. Otherwise this node is the lowest common ancestor
    else return node.val;
  }
}

def solve(root, p, q):
    # 1. Walk down from the root, which is an ancestor of every node
    node = root
    while True:
        # 2. Both values are smaller than this node: go to its left child
        if p < node.val and q < node.val:
            node = node.left
        # 3. Both values are larger than this node: go to its right child
        elif p > node.val and q > node.val:
            node = node.right
        # 4. Otherwise this node is the lowest common ancestor
        else:
            return node.val

Example 2, traced

Input
root = {"val":6,"left":{"val":2,"left":{"val":0,"left":null,"right":null},"right":{"val":4,"left":{"val":3,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}},"right":{"val":8,"left":{"val":7,"left":null,"right":null},"right":{"val":9,"left":null,"right":null}}}
p = 2
q = 4

Output
2

Why it works

The node you stand on is always an ancestor of both values: the root is, and you step down only to the side that holds both. When the walk stops, the two values are not both under one child, so no lower node is an ancestor of both. The node you stopped on is the lowest.

Time and space

Time O(h), extra space O(1). Each round moves one step down the tree, so there are at most h rounds, where the height h counts the nodes on the longest path from the root down: O(h) time. Only the current node is kept and nothing is recursive, so the extra space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Compare with strictly smaller and strictly larger. If a value equal to the node counts as lying on one side, the walk steps past a node that is p or q itself, and example 2 returns 3 instead of 2.
• Move only when both values are on the same side. Following p alone leads all the way down to p, and example 1 returns 2 instead of 6.
• Do not assume that p is the smaller value. The two can come in either order, and code that relies on p being smaller can walk off the bottom of the tree.

Pattern

Binary search tree ordering. Builds on Binary Search.

Keep going