Lowest Common Ancestor Family

PracticalmediumPremium

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

Lowest common ancestor (LCA) shows up everywhere: reporting the lowest manager shared by two people in an org chart, computing the merge-base of two git commits, and finding the shared container of two DOM nodes before re-parenting a subtree. You are given a tree of integer ids where every id maps to its parent id - the root's entry is None (Python) or null (JavaScript/TypeScript) - and must answer LCA queries for pairs, lists, and long batches of ids.

You implement an LCASolver class. The constructor receives the parent map and is your one chance to preprocess. Level 1 starts inside a binary search tree where value ordering lets you prune; Level 2 drops that guarantee; Level 3 hands you nothing but raw parent pointers; Level 4 extends to many nodes at once in an n-ary org chart; Level 5 makes the queries arrive in bulk, so preprocessing pays.

Level 1 - Binary search trees

Ids are BST values and the tree was built with BST ordering, so the classic insight applies: if both target values are smaller than the current node, go left; if both are larger, go right; the moment the pair straddles the current node - or one target equals it - that node is the answer. Walking from the root, the LCA of two leaves is simply the first node where their paths split.

On the 6-node tree below, lca(4, 5) walks from the root: both 4 and 5 descend into subtree 2, and once inside, 4 and 5 sit on opposite sides of 2 - one in its left child, one in its right child - so 2 is the deepest node whose subtree contains both.

        1
      /   \
     2     3
    / \      \
   4   5      6
 
lca(4, 5):
  at 1: both 4 and 5 descend into subtree 2 -> step into 2
  at 2: 4 and 5 sit on opposite sides of 2 -> answer: 2

Level 2 - General binary trees

Distinct values, but no ordering guarantee: children ids may be smaller, larger, or completely unrelated to their parent. Value-comparison pruning is gone, so you must genuinely trace the tree - find both paths from the root (or walk parent pointers up from each node until the paths first intersect). The structure you receive is still just the parent map, so the robust move is the same as Level 3: know each node's depth, then align and walk.

On the tree below, ids deliberately refuse to sort: 30 and 7 are children of 4, which is a child of 25's smaller sibling. lca(19, 7) = 4 even though neither comparison at the root would suggest it, because 19's parent chain (30 → 4) and 7's parent chain (4) first meet at 4.

def lca(self, a: int, b: int) -> int:
    """Return the lowest common ancestor of a and b."""

Level 3 - Parent pointers only

Your solver receives nothing but the parent map - no children lists, no root handle, no precomputed depths. The workhorse algorithm for every remaining level is: resolve each node's depth by climbing parent pointers to the root, then answer queries by lifting the deeper node up until depths are equal, and finally walking both nodes up in lockstep until they meet. On a 1000-node chain 1 ← 2 ← 3 ← ... ← 1000, lca(900, 400) lifts 900 up five hundred depth steps to 400's level - arriving exactly at 400 - and the lockstep walk confirms it immediately.

The chain shape is the trap: a recursive solution blows the call stack on a 1000-deep chain, and a per-query walk over the whole tree is wasted work when the depth-align walk only touches the two paths.

def __init__(self, parent: dict[int, int | None]) -> None:
    """Preprocess the parent map so later queries only pay O(depth)."""

Level 4 - Org charts

Real org charts are n-ary: the CEO manages many VPs, each VP manages many engineers. Your parent map already encodes this - an employee id maps to their manager id - and lca_many answers the shared-manager question for a list of two or more employees. LCA is associative, so fold pairwise: lca(lca(a, b), c). The fold's running result is always an ancestor-or-self of every id processed so far, which is why processing order never changes the answer.

In the org chart below, 7 and 5 both report (transitively) to manager 2, and 6 reports to manager 3. The fold of lca_many([7, 5, 6]) is lca(lca(7, 5), 6) = lca(2, 6) = 1 → the CEO, the lowest node managing all three.

            1 (CEO)
          /   \
         2     3
        / \   / \
       4   5 6   8
      /
     7
 
lca_many([7, 5, 6]):
  lca(7, 5) = 2         # 7 and 5 share manager 2
  lca(2, 6) = 1         # 2 and 3 are siblings -> CEO

def lca_many(self, ids: list[int]) -> int:
    """Return the lowest common ancestor of every id in the list."""

Level 5 - Batched queries

One static tree, many queries. answer_queries(queries) receives the whole batch at once, reusing whatever the constructor preprocessed - most importantly each node's depth, memoized during preprocessing. That turns each query into pure pointer-chasing: O(depth) time, zero rebuilding. The depth map is computed exactly once in the constructor; every one of the 500 queries below reuses it.

For the 9-node query tree, three representative queries and their answers:

Query	Why	Answer
`(9, 9)`	Same node twice	`9`
`(10, 6)`	10's parent chain is 10 → 6; meets 6's own chain at 6	`6`
`(8, 5)`	8 climbs to 4 → 2; 5 also sits under 2	`2`

On a 2000-node chain, the preprocessed solver answers each of 100 queries with two O(depth) climbs and nothing more - a solver that recomputed depths per query would pay the climb twice over.

def answer_queries(self, queries: list[tuple[int, int]]) -> list[int]:
    """Answer every (a, b) query, reusing preprocessed data."""

Loading editor...

The live editor for this challenge unlocks with Premium.

Browse free problems

0/0 passed