Build a Tree and Perform BFS Traversal

Tree Level Order from Parent-Child Pairs Medium · Tree, Breadth-First Search, Hash Table · Company Tags · Hints

You are given a list of directed edges that uniquely defines a tree. Each edge is represented as a two-element array [parent, child], meaning there is a connection from node parent to node child. All edges together form a valid tree with exactly one root (a node that is never a child). Every node has a unique integer value.

Your task is to reconstruct the tree from the edge list and then perform a level‑order traversal (also known as breadth‑first search). Return an array containing the node values in the order they are visited during the traversal.

Traversal ordering rule: When you visit a node, its children must be processed in the same relative order that they appear in the given edges list for that parent. In other words, scan the input from left to right; the first time you see a parent, its first child becomes the first child of that parent in the output, and so on.

Example 1:

Input: edges = [[1,2],[1,3],[2,4],[2,5]]

Output: [1,2,3,4,5]

Explanation: The root is 1. Its children in input order are 2 then 3. Next, 2’s children are 4 then 5. Therefore the level‑order sequence is 1, then 2, 3, then 4, 5.

Example 2:

Input: edges = [[3,1],[3,2]]

Output: [3,1,2]

Example 3:

Input: edges = [[5,4],[4,3],[3,2],[2,1]]

Output: [5,4,3,2,1]

Constraints:

• 1 <= edges.length <= 5000
• -100,000 <= node value <= 100,000
• All node values are distinct.
• The edges form a single tree with exactly one root and no cycles.