Find the Lowest Common Ancestor of Two Nodes in an N-ary Tree
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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:
```text
0
/ | \
1 2 3
/ \ \
4 5 6
|
7
```
**Example 1**
```text
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**
```text
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**
```text
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`.
Overview: 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.
Implement `lowest_common_ancestor(children, p, q)`, which returns that label as an integer.
### 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`.
- Every label and the returned value are less than `10^5`, so no value exceeds `2^31 - 1`; a 32-bit `int` suffices in Java and C++.
### Examples
Both examples use the tree `children = [[1, 2, 3], [4, 5], [], [6], [], [7], [], []]`: node `0` has children `1`, `2` and `3`; node `1` has children `4` and `5`; node `3` has child `6`; node `5` has child `7`.
**Example 1**
```text
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**
```text
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`.
Constraints
- 1 <= n <= 10^5, where n = len(children)
- 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.
- Every node except the root 0 appears in exactly one children list and 0 appears in none, so the input is a single tree rooted at 0.
- The tree can be a single path, so its depth can reach n - 1.
- All labels and the answer are below 10^5 and fit in a signed 32-bit integer.
Examples
Input: ([[]], 0, 0)
Expected Output: 0
Explanation: Minimum valid tree: a single root queried with p == q == 0.
Input: ([[1], []], 1, 0)
Expected Output: 0
Explanation: Two-node tree: the root is an ancestor of node 1, so the root is returned.
Hints
- 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.
- 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.
- 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.