Katkat
Back

Find the Lowest Common Ancestor of Two Nodes in an N-ary Tree

BloombergSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Given a rooted tree whose nodes can have any number of children, stored as child lists, return the lowest common ancestor of two labeled nodes. The problem generalizes the binary-tree version to arbitrary fan-out and tests tree traversal, ancestor reasoning, and robust handling of very deep, path-shaped trees.

You are given a rooted tree in which every node may have any number of children (an N-ary tree). The nodes are labeled 0 to n - 1, node 0 is the root, and children[i] lists the children of node i. Given two node labels p and q, return the label of their lowest common ancestor.

The lowest common ancestor of p and q is the deepest node whose subtree contains both p and q, where every node is considered part of its own subtree. Equivalently, it is the ancestor of both nodes that lies farthest from the root, with each node counted as an ancestor of itself.

This is the familiar binary-tree version of the problem, extended to nodes with an arbitrary number of children.

Function Signature

def lowest_common_ancestor(children: list[list[int]], p: int, q: int) -> int:

Rules

  • n = len(children). Every node except the root appears in exactly one children list, and the root 0 appears in none, so the input always describes a single tree rooted at 0.
  • Labels do not follow any traversal order: a child may have a smaller label than its parent.
  • A node is an ancestor of itself. If p is an ancestor of q, the answer is p, and if p == q, the answer is p.
  • The order of labels inside a children list has no effect on the answer.
  • Any two nodes of a tree have exactly one lowest common ancestor, so the answer is unique.

Constraints

  • 1 <= n <= 10^5
  • 0 <= p <= n - 1 and 0 <= q <= n - 1
  • Every label in children is in the range [0, n - 1], and the lists together contain exactly n - 1 labels.
  • The tree can be a single path, so its depth can reach n - 1.

Examples

All three examples use this tree:

 0
 / | \
 1 2 3
 / \ \
 4 5 6
 |
 7

Example 1

Input: children = [[1, 2, 3], [4, 5], [], [6], [], [7], [], []], p = 4, q = 7
Output: 1

The ancestors of 4 are 4, 1, 0 and the ancestors of 7 are 7, 5, 1, 0. The deepest node they share is 1.

Example 2

Input: children = [[1, 2, 3], [4, 5], [], [6], [], [7], [], []], p = 7, q = 6
Output: 0

7 lies under 1 and 6 lies under 3, so the only shared ancestor is the root.

Example 3

Input: children = [[1, 2, 3], [4, 5], [], [6], [], [7], [], []], p = 5, q = 7
Output: 5

5 is an ancestor of 7, and every node counts as its own ancestor, so the answer is 5.