Group Tree Nodes into Layers from the Leaves Up to the Root

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

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]]

Tree Layers from Leaves to Root

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]]

Hints

1. 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.
2. 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.
3. 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.

Approach

The layer of a node is exactly its height in the tree rooted at root: leaves have height 0, and any other node has height 1 + the largest height among its children. So the task is to compute every node's height and bucket nodes by it.

1. Build an adjacency list from the undirected edges (orientation in the input means nothing).
2. Run an iterative breadth-first search from root, recording each node's parent and the visiting order. BFS order puts every parent before all of its children.
3. Walk that order backwards. When a node is reached, all of its descendants have already been processed, so its height is final; push height[u] + 1 up to its parent if it is larger than what the parent has so far. Leaves never receive an update and stay at 0.
4. The root's height is the largest, so there are height[root] + 1 layers. Along the path from the root to its deepest leaf the heights take every value from height[root] down to 0, so no layer is empty.
5. Scan labels 0 to n - 1 in increasing order and append each to its layer; each layer is then already in ascending order without sorting.

Everything is iterative, so a path of 100000 nodes (height 99999) causes no stack overflow, and each node and edge is touched a constant number of times.

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