Closest shared ancestor in a search tree

Trees Mid-level Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

tree = {6: (2, 8), 2: (0, 4), 8: (7, 9), 4: (3, 5)}
a, b = 3, 5
node = 6
while True:
    if a < node and b < node:
        node = tree[node][0]
    elif a > node and b > node:
        node = tree[node][1]
    else:
        break
print(node)

Options426

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 4

Right: 3 and 5 both go left at 6, both go right at 2, then split at 4.

The walk stops at the first value between the two targets, which is the deepest node holding both.

Why not the others?

B 2. Both 3 and 5 are larger than 2, so the walk continues right.
C 6. Both values are smaller than 6, so the answer is below it.

30-second answer

Start at the root. If both values are smaller, the answer is in the left subtree; if both are larger, it is in the right. Otherwise the values split here (or one equals this node), so this node is the answer. O(h) time (O(log n) when balanced, O(n) for a chain), O(1) space with a loop.

Practise saying it · 45 s. No recording, just a timer

Explain the shared-ancestor walk in a search tree.

Say your answer out loud, then check which of these points you covered:

Both smaller: go left
Both larger: go right
Split point is the answer

Deep dive

The search-tree order lets you skip whole subtrees; a general binary tree needs a full O(n) search.

The split point is the first node whose value lies between the two targets, inclusive.

In a general tree, recurse and return the node where both sides report a find.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

def shared_ancestor(root: Node | None, a: int, b: int) -> int:
    node = root
    while node is not None:
        if a < node.val and b < node.val:
            node = node.left
        elif a > node.val and b > node.val:
            node = node.right
        else:
            return node.val
    raise ValueError("values not in the tree")

Common mistakes

Searching both values separately and comparing paths, which works but uses O(h) extra space.
Forgetting that a node can be its own ancestor.

Senior take & follow-ups

Say why the first split point is the answer: any lower node would miss one of the values.

Follow-up questions

Think of your answer first, then open the hint.

What about a general binary tree?
Show hint
Post-order: return the node if found; a node whose two sides both return something is the answer.
How would you answer many queries fast?
Show hint
Binary lifting or an Euler tour with range minimum queries.

What each operation costs: Binary Tree · Binary Search Tree · Tree Traversal

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.