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

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.

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

Hints

1. A node counts as its own ancestor, so when p == q, or when one of p and q lies on the other's path to the root, that node is the answer.
2. Labels carry no traversal order and the order inside a children list does not matter, so do not infer depth or ancestry from label values or list positions.
3. The tree can be a single path of depth n - 1 (up to 10^5 - 1), so think about how deep any recursion in your approach could go.

Approach

Algorithm: scan every children list once and record parent[c] = i for each label c in children[i]; the root keeps parent -1. Walk from p up to the root, marking every node on that path, p included; the marked set is exactly the ancestors of p. Then walk upward from q and return the first marked node.

Invariant and correctness: the walk from q visits the ancestors of q in order from deepest to shallowest, q first. The first one that is also marked is therefore the deepest node that is an ancestor of both p and q, which is the lowest common ancestor by definition. The walk always stops, because the root is an ancestor of every node and is always marked.

Edge cases: because each node counts as its own ancestor, p == q stops immediately at q, and when one query node is an ancestor of the other the walk returns that node. Labels are never compared by value and list order is never used, so children with smaller labels than their parents and any permutation of a children list give the same answer. Both walks are iterative, so a single path of depth n - 1 cannot overflow a call stack. The smallest input, children = [[]] with p = q = 0, returns 0.

• Time complexity: O(n)
• Space complexity: O(n)