Group Tree Nodes into Layers from the Leaves Up to the Root
Company: Vercel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
You are given a rooted tree with `n` nodes labeled `0` to `n - 1`. The tree is described as an undirected graph: `edges` lists its `n - 1` edges, and `root` is the node the tree hangs from. Print the nodes from the leaves up to the root, layer by layer: every leaf first, the root last, and every node only after all of its children.
Return the layers as a list of lists.
### Function Signature
```python
def leaves_to_root_layers(n: int, edges: list[list[int]], root: int) -> list[list[int]]:
```
### Rules
- Root the tree at `root`. The children of a node are its neighbors other than its parent.
- A leaf is a node with no children. Every leaf is in layer `0`.
- A node with children is in layer `1 + max(layer of each child)`.
- The answer lists the layers in order `0, 1, 2, ...`. It therefore ends with a layer that contains only `root`.
- Within a layer, node labels appear in ascending order.
- With `n = 1`, the root has no children, so it is a leaf and the answer is `[[0]]`.
### Constraints
- `1 <= n <= 100000`
- `len(edges) == n - 1`
- Each `edges[i]` is `[a, b]` with `0 <= a < n`, `0 <= b < n` and `a != b`, describing an undirected edge.
- The edges form a tree: all nodes are connected, and there are no cycles and no duplicate edges.
- `0 <= root < n`
- The tree may be a single path, so its height can be as large as `n - 1`.
### Examples
**Example 1**
- Input: `n = 7`, `edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [5, 6]]`, `root = 0`
- Output: `[[3, 4, 6], [1, 5], [2], [0]]`
- Explanation: Nodes `3`, `4` and `6` are leaves. Node `1` has children `3` and `4`, and node `5` has child `6`, so both are in layer `1`. Node `2` has child `5`, so it is in layer `2`. The root `0` has children in layers `1` and `2`, so it is in layer `3`. Leaf `6` is deeper in the tree than node `1`, but as a leaf it is still printed first.
**Example 2**
- Input: `n = 5`, `edges = [[0, 3], [3, 4], [2, 0], [1, 0]]`, `root = 3`
- Output: `[[1, 2, 4], [0], [3]]`
- Explanation: Rooted at `3`, node `3` has children `0` and `4`, and node `0` has children `1` and `2`. Nodes `1`, `2` and `4` are leaves, node `0` is in layer `1`, and the root is in layer `2`.
**Example 3**
- Input: `n = 1`, `edges = []`, `root = 0`
- Output: `[[0]]`
Overview: Given a rooted tree described as an undirected edge list, return its nodes in layers from the leaves up to the root, where each node sits one layer above its highest child and each layer is sorted. It tests rooting a tree from a graph, bottom-up ordering, and handling very deep, path-shaped trees.
You are given a tree with `n` nodes labeled `0` to `n - 1`, described as an undirected graph by its `n - 1` edges, together with a node `root` that the tree hangs from. Output the nodes from the leaves up to the root, one layer at a time: every leaf comes first, the root comes last, and every node appears only after all of its children.
Return the layers as a list of lists.
### Rules
- Root the tree at `root`. The children of a node are its neighbors other than its parent. Edge orientation carries no meaning: `[a, b]` and `[b, a]` describe the same edge.
- A leaf is a node with no children. Every leaf is in layer `0`.
- A node with children is in layer `1 + max(layer of each child)`.
- List the layers in order `0, 1, 2, ...`. The answer therefore ends with a layer containing only `root`, and no layer is empty.
- Within a layer, node labels appear in ascending order.
- With `n = 1` the root has no children, so it is a leaf and the answer is `[[0]]`.
### Constraints
- `1 <= n <= 100000`
- `len(edges) == n - 1`
- Each `edges[i]` is `[a, b]` with `0 <= a < n`, `0 <= b < n` and `a != b`, describing an undirected edge.
- The edges form a tree: all nodes are connected, and there are no cycles and no duplicate edges.
- `0 <= root < n`
- The tree may be a single path, so its height can be as large as `n - 1`.
All labels and layer indices are below `100000`, so every value fits in a 32-bit signed integer.
### Examples
**Example 1**
- Input: `n = 7`, `edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [5, 6]]`, `root = 0`
- Output: `[[3, 4, 6], [1, 5], [2], [0]]`
- Explanation: Nodes `3`, `4` and `6` are leaves. Node `1` has children `3` and `4`, and node `5` has child `6`, so both are in layer `1`. Node `2` has child `5`, so it is in layer `2`. The root `0` has children in layers `1` and `2`, so it is in layer `3`. Leaf `6` sits deeper in the tree than node `1`, but as a leaf it is still output first.
**Example 2**
- Input: `n = 5`, `edges = [[0, 3], [3, 4], [2, 0], [1, 0]]`, `root = 3`
- Output: `[[1, 2, 4], [0], [3]]`
- Explanation: Rooted at `3`, node `3` has children `0` and `4`, and node `0` has children `1` and `2`. Nodes `1`, `2` and `4` are leaves, node `0` is in layer `1`, and the root is in layer `2`.
**Example 3**
- Input: `n = 1`, `edges = []`, `root = 0`
- Output: `[[0]]`
Constraints
- 1 <= n <= 100000
- len(edges) == n - 1
- Each edges[i] is [a, b] with 0 <= a < n, 0 <= b < n and a != b (undirected; either orientation)
- The edges form a tree: connected, no cycles, no duplicate edges
- 0 <= root < n
- The tree may be a single path, so its height can be as large as n - 1
Examples
Input: (7, [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [5, 6]], 0)
Expected Output: [[3, 4, 6], [1, 5], [2], [0]]
Input: (5, [[0, 3], [3, 4], [2, 0], [1, 0]], 3)
Expected Output: [[1, 2, 4], [0], [3]]
Hints
- A node's layer is its height in the rooted tree: the number of edges on the longest downward path from it to a leaf. It has nothing to do with its depth from the root.
- Edge direction in the input is meaningless. Discover each node's parent by walking outward from root, and avoid recursion: a path of 100000 nodes will overflow a recursive DFS.
- If you process nodes in reverse breadth-first order, every child is finished before its parent, so each parent can take 1 + the max over its children in one pass. Then scan labels 0..n-1 to fill the layers already sorted.