Katkat
Back

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

VercelSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

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