Lowest common ancestor

Where do two nodes' paths from the root split? A search tree answers by comparing values, any tree by one search, and a fixed tree asked many times by jumping 1, 2, 4, 8 levels at once.

3 examples12 to practiceRead · 5 min
The idea

Two nodes meet where their paths from the root split

A node's ancestors are its parent, its parent's parent and so on up to the root; by convention a node also counts as its own ancestor. The lowest common ancestor (LCA) of two nodes is the deepest node that is an ancestor of both.

1234589

The paths from the root to 4 and to 8 share 1 and 2, then split. Their lowest common ancestor is 2.

The rule

Follow the paths from the root to both nodes. They share every node down to the lowest common ancestor and no node after it, so the LCA is the last node the two paths have in common.

It answers questions like which folder contains both of two files, which manager two employees share, or how far apart two nodes are: the distance is depth(a) + depth(b) − 2 × depth(LCA), because the route between them goes up to the meeting point and back down.

Basic

In a search tree, the values tell you which way to go

In a binary search tree you don't need to search. If both values are smaller than the current node, both are in its left subtree, and so is their meeting point; if both are larger, go right. The first node where they fall on different sides, or where the node is one of the two values, is the answer.

Medium

Without an order, each subtree reports what it found

In an ordinary binary tree there is no way to know which side a value is on, so search both. Each call returns the node it found below it: one of the two values, or nothing. A node that hears back from both sides is where the paths split, so it is the answer, and it is passed up unchanged from there. A node that is itself one of the values returns at once: if the other value is below it, it is the answer anyway.

This assumes both values are in the tree. If one might be missing, the search has to keep going past the first match to confirm the other exists.

Hard

For many questions, precompute jumps of 1, 2, 4, 8 levels

When the tree is fixed and the questions keep coming, an O(n) search per question is too slow. With parent links you could instead lift the deeper node until both are at the same depth, then step both up one level at a time until they meet, but that is O(h) per question, and h can be n.

Binary lifting speeds up the climbing. Precompute, for every node, its ancestor 1, 2, 4, 8, … levels up: row j of a table holds each node's ancestor 2ʲ levels up, and each row is built from the one before, since two jumps of 2ʲ⁻¹ make one jump of 2ʲ. Then any climb is a few jumps, one per binary digit of the distance.

A question then goes in two phases. First lift the deeper node by exactly the depth difference. Then, from the largest jump down to the smallest, jump both nodes together whenever they would land on different nodes: landing on the same node might overshoot the lowest meeting point. When no jump is left, the two nodes are just below their lowest common ancestor.

Choosing

Pick by what the tree gives you and how many questions there are

What you have

Approach

Cost

A binary search tree

Walk down by comparing values

O(h) per question

Any binary tree, one question

Search both sides, report finds upward

O(n)

Parent links and depths

Lift the deeper node, then step both up

O(h) per question

A fixed tree and many questions

Binary lifting

O(n log n) to build, O(log n) per question

Check yourself

4 questions

1. In a binary search tree, both values are larger than the current node. Where is their lowest common ancestor?
2. What is the lowest common ancestor of a node and one of its own descendants?
3. In binary lifting, why jump both nodes only when they would land on different nodes?
4. How far apart are two nodes at depths 5 and 3 whose lowest common ancestor is at depth 1?
Takeaways

Remember this

  • The lowest common ancestor is the deepest node that is an ancestor of both; a node counts as its own ancestor.
  • In a search tree, walk down while both values are on the same side; the first split is the answer, O(h).
  • In any binary tree, each subtree reports what it found; the node that hears from both sides is the answer, O(n).
  • Binary lifting stores each node's ancestors 1, 2, 4, … levels up, so a fixed tree answers each question in O(log n).
  • The distance between two nodes is depth(a) + depth(b) − 2 × depth(LCA).
Practice

Now solve some yourself

Only this topic 0 of 6 solved

  1. Medium
    Directions from one node to another as steps
    Lowest common ancestor
    LeetCode 2096(opens in a new tab)
  2. Medium
    The boss k levels above an employee
    Lowest common ancestor
    CSES 1687(opens in a new tab)
  3. Medium
    The lowest common boss of two employees
    Lowest common ancestor
    CSES 1688(opens in a new tab)
  4. Hard
    The kth ancestor of a node, asked many times
    Lowest common ancestor
    LeetCode 1483(opens in a new tab)
  5. Hard
    Distances between pairs of nodes in a tree
    Lowest common ancestor
    CSES 1135(opens in a new tab)
  6. Hard
    Cycle lengths when an extra link joins two nodes
    Lowest common ancestor
    LeetCode 2509(opens in a new tab)

Mixed with topics you have practiced 0 unlocked

    6 more once you have practiced Tree traversals, BFS & DFS, Graphs & representations. Play one of its examples to the end and solve one of its problems to unlock them.

    Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.

    Next

    Segment & Fenwick trees

    Continue