Where it runs
1. The problem
Two people work in the same company. You want their nearest common manager: the team lead or director who has both of them somewhere below, with no such person lower down. Walk up the chain of managers from each of the two. The answer is the first place where the two paths meet.
The same problem comes up on any tree. Given two files, you want the deepest folder that holds both. Given two categories in a product catalog, you want the narrowest group that contains both. Given two commits, you want the point in history where they split from a shared ancestor.
This deepest shared ancestor is called the lowest common ancestor (LCA). A node counts as its own ancestor. So if one of the two nodes sits directly above the other, the answer is the upper node.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedlca(root, 6, 4) // root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]Find the lowest common ancestor of p = 6 and q = 4. Every call asks one question: does a target sit in my subtree?
Recognise it
Say these words and it is this pattern
- lowest common ancestor of two nodes
- deepest node that is an ancestor of both p and q
- each recursive call returns which target(s) it found below it
- path from root to each node then compare (alternate approach)
- binary tree or BST given, find where the two paths split
Looks similar, isn't
- Binary search tree
In a search tree the values alone point the way. In a plain tree both subtrees must be asked.
- Tree traversal
That page is about the three visit orders. This uses post-order to answer one question.
- Union-find (disjoint set)
Tarjan's offline algorithm answers many pairs with a disjoint set. A single pair does not need it.
- DP on trees
DP on trees carries computed values upward. Here the thing carried up is only found or not found.
n nodes give O(n) for one query. Many queries want binary lifting, at O(log n) each.
On LeetCode
Problems about where two nodes of a tree meet, or the path between them. One postorder pass returns whatever each side found, and the node where both sides report is the answer.
The lesson task under the same name.
In a search tree the values decide the side, so go left while both are smaller, right while both are bigger, and stop where they split.
Return the depth along with the node, and when both sides are equally deep the current node is the answer.
Find the path from the root to each node, cut the common start, which ends at the LCA, then turn the first path into U moves.