Lowest Common Ancestor of a Binary Search Tree

The problem

You are given the root of a binary search tree (BST) and two of its nodes, first_node and second_node. In a BST, every value in the left subtree of a node is smaller than the node, and every value in the right subtree is larger.

Return their lowest common ancestor: the lowest node in the tree that has both first_node and second_node in its subtree. A node counts as part of its own subtree, so first_node itself can be the answer.

Trees in the examples are written level by level, from left to right. null marks a missing child.

Example 1

Input: root = [8, 4, 12, 2, 6, 10, 14, null, null, 5, 7], first_node = 5, second_node = 7

Output: 6

5 and 7 are the two children of 6. Nodes 4 and 8 hold them too, but 6 is lower.

Example 2

Input: root = [8, 4, 12, 2, 6, 10, 14, null, null, 5, 7], first_node = 4, second_node = 7

Output: 4

7 is in the subtree of 4, and 4 counts as its own ancestor. So 4 is the answer.

Example 3

Input: root = [3, 1], first_node = 3, second_node = 1

Output: 3

1 is the left child of 3. The root holds both.

Constraints

• The tree has n nodes, where 2 ≤ n ≤ 100,000.
• -1,000,000,000 ≤ Node.val ≤ 1,000,000,000
• All values are different.
• first_node and second_node are different, and both are in the tree.

Clarifying questions

Can first_node be the ancestor of second_node?

Yes. Then first_node itself is the answer, because a node counts as its own ancestor.

Are first_node and second_node always in the tree?

Yes. So we never have to report "not found".

Can values repeat?

No. All values are different, so comparing values is enough to tell where a node lives.

Is first_node always smaller than second_node?

No. The order is not given, so the checks must work either way.

Spot the pattern

The tree is a BST, so one comparison tells which side a value lives on. If first_node and second_node are both on one side of a node, the answer is on that side too. That turns a search over the whole tree into a single path from the root down, a tree traversal that visits one node per level.

Solutions

Brute forceO(n)OptimalO(h)

Show all

This problem has two approaches. There is no useful step between them.

Brute force O(n)

The idea

Forget the BST order and solve it for any binary tree. Each call searches one subtree and returns what it found there: first_node, second_node, their common ancestor, or nothing.

A call on first_node or second_node returns that node at once. A call on any other node asks both children. If both sides found something, then first_node is on one side and second_node on the other, so this node is the lowest one above both. If only one side found something, the call passes it up.

It is correct, but it may visit every node, even in parts of the tree where first_node and second_node cannot be.

Walkthrough

call stack top →

empty

nodes visited

0

1. def lowest_common_ancestor(node, first_node, second_node):
2. if node is None or node is first_node or node is second_node:
3. return node
4. found_left = lowest_common_ancestor(node.left, first_node, second_node)
5. found_right = lowest_common_ancestor(node.right, first_node, second_node)
6. if found_left and found_right:
7. return node
8. return found_left or found_right

Find the lowest node with both first_node = 5 and second_node = 7 under it. This version ignores the BST order and searches like in any tree. Under a finished node, →5 is what it returned, and →∅ means nothing.

← BackStep →Play1 / 15

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: search the whole tree like any binary tree, ignoring
    // the BST order. Every node may be visited, so n steps.
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode firstNode, TreeNode secondNode) {
        // Report firstNode or secondNode when we reach it. Nothing below it can be a
        // lower common ancestor than the node itself.
        if (root == null || root.val == firstNode.val || root.val == secondNode.val) return root;
        TreeNode foundLeft = lowestCommonAncestor(root.left, firstNode, secondNode);
        TreeNode foundRight = lowestCommonAncestor(root.right, firstNode, secondNode);
        // One found on each side: this is the first node above both.
        if (foundLeft != null && foundRight != null) return root;
        // Otherwise pass up whatever was found, if anything.
        return foundLeft != null ? foundLeft : foundRight;
    }
}

Big O

Time O(n)Space O(h)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There is no loop. The work repeats through recursion, so we count the calls. Each call does a fixed job: a few checks and at most two more calls. So each call counts as 1 step.

   1. def lowest_common_ancestor(node, first_node, second_node):
   2. if node is None or node is first_node or node is second_node:
   3. return node
   4. found_left = lowest_common_ancestor(node.left, first_node, second_node)
   5. found_right = lowest_common_ancestor(node.right, first_node, second_node)
   6. if found_left and found_right:
   7. return node
   8. return found_left or found_right

2. 2 Count the runs on Example 1

   The picture numbers each call in order. All 9 nodes get a call. The leaves 2, 10 and 14 also call their 2 empty children each, which return at once. 5 and 7 return before they look at their children.

   9 node calls + 6 empty calls = 15 calls.

   total calls

   9 nodes + 6 empty children = 15

3. 3 Write the count for any n

   In the worst case, first_node and second_node are deep and the search reaches every node. Then each of the n nodes gets one call, and so does each of the n + 1 empty child spots.

   n + (n + 1) = 2n + 1 calls

   Check it with Example 1: the bound is 2 × 9 + 1 = 19. The real run used 15, because it stopped at 5 and 7 without calling their children.

4. 4 Keep only the part that grows fastest

   • Drop the + 1. One call more does not change the growth.
   • Drop the 2. When n doubles, 2n doubles too.

   What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code makes no list or map. The memory is the call stack, the calls that started and have not returned yet. At most h wait at once, where h is the height of the tree. In Example 1, h is 4. In a chain-shaped tree, h = n. So the space is O(h).

   call stack (one frame per level)

Very deep trees

Each recursive call waits until the calls below it finish. If the tree is one long line of 100,000 nodes, that is 100,000 calls waiting at once. The algorithm is still right, but every language limits how many calls can wait, so a very deep tree can crash with a "stack overflow". Here is how to raise the limit:

• Python: stops at 1,000 calls. The code above raises it with sys.setrecursionlimit.
• Java: run with java -Xss64m, or run the work in new Thread(null, task, "main", 64L << 20).
• C#: run the work in new Thread(task, 64 * 1024 * 1024).
• TypeScript (Node): run with node --stack-size=30000.
• Go: nothing to do. Its stack grows by itself.

At 100,000 levels, Node crashes even with a raised limit. The optimal approach walks down in a loop, so it never has this problem.

Recursion is still the answer interviewers expect for trees. Mention the limit out loud: "for a very deep tree, I would raise the stack limit or keep my own stack in a loop."

Optimal O(h)

The idea

Start at the root and compare both values with it.

• Both are smaller: both live in the left subtree, so the answer is there too. Go left.
• Both are larger: go right, for the same reason.
• Anything else: they split here. One is on the left and one on the right, or one of them is this very node. Return it.

The walk never needs to come back up, so a plain loop does it. No recursion, no stack.

Why it never misses the answer: while both values are on one side, every node on the other side holds neither of them, so it cannot be a common ancestor. At the split node, any node lower down sits on one side only, so it holds at most one of the two. The split node is the lowest one that holds both.

Walkthrough

first_node, second_node

57

1. node = root
2. while node:
3. if first_node.val < node.val and second_node.val < node.val:
4. node = node.left
5. elif first_node.val > node.val and second_node.val > node.val:
6. node = node.right
7. else:
8. return node

Start at the root. In a BST, smaller values live on the left and larger ones on the right. Use that to head for first_node = 5 and second_node = 7 together.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // BST walk: go down from the root toward both values at once.
    // The first node that splits them is the answer. One node per level.
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode firstNode, TreeNode secondNode) {
        TreeNode node = root;
        while (node != null) {
            // Both are smaller, so both live in the left subtree.
            if (firstNode.val < node.val && secondNode.val < node.val) node = node.left;
            // Both are larger, so both live in the right subtree.
            else if (firstNode.val > node.val && secondNode.val > node.val) node = node.right;
            // They split here, or one of them is this node. Any lower
            // node would hold only one of them.
            else return node;
        }
        return null;
    }
}

Big O

Time O(h)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The loop body runs once per node on the path down. Each run does two or four comparisons and one move. That is the same small job every time, so each run counts as 1 step.

   1. node = root
   2. while node:
   3. if first_node.val < node.val and second_node.val < node.val:
   4. node = node.left
   5. elif first_node.val > node.val and second_node.val > node.val:
   6. node = node.right
   7. else:
   8. return node

2. 2 Count the runs on Example 1

   Example 1 visits 8, then 4, then 6, one node on each of the first 3 levels. At 6 the values split, and the loop returns.

   3 runs.

   run	1	2	3
   node	8	4	6
   level	1	2	3
   result	go left	go right	split: return

3. 3 Write the count for any n

   Every run moves one level down, and it never goes back up. So the loop runs at most once per level. Let h be the height of the tree, the number of levels on the longest path down:

   at most h runs

   Check it with Example 1: h is 4, and the loop ran 3 times.

4. 4 Keep only the part that grows fastest

   There is nothing to drop: the count is already h. How big h is depends on the shape. A balanced BST has h about log n, which is only 17 for 100,000 nodes. A BST built from sorted values is a chain, and then h = n. So the time is O(h): O(log n) when balanced, O(n) in the worst case.

   So the time is O(h).

5. S Space: count the extra memory the same way

   The loop keeps only node. It is one variable, whatever the size of the tree, so the space is O(1).

   node

Common mistake

Comparing only one of the two values

Going left because first_node is smaller than the node is wrong when second_node is larger. That node is where they split, so it is the answer. Move only when both values are on the same side.

Tested at the limits

2,000 random search trees of 2 to 10 values, built by inserting the values in random order, with a random pair of nodes. The brute force and the optimal solution gave the same answer every time.

Largest inputs	Result
100,000 nodes in one long line (the most allowed), asking about the two deepest nodes. Optimal.	0.01 s, and under 0.01 MB of extra memory: one pointer walks down in a loop, which is the O(1) space.
100,000 nodes, balanced, asking about two nodes near the bottom. Optimal.	Under 0.001 s, and under 0.01 MB of extra memory: the walk goes down only about 17 levels.
100,000 nodes in one long line. Brute force.	0.03 s, and about 15 MB of extra memory: 100,000 calls wait at once, which is the O(h) space. The optimal loop needs none of that.