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.