N-ary Tree Level Order Traversal

LeetCode 764 | Difficulty: Medium

Medium

Problem Description

Given an n-ary tree, return the level order traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

Constraints:

- The height of the n-ary tree is less than or equal to `1000`

- The total number of nodes is between `[0, 10^4]`

Topics: Tree, Breadth-First Search

---

Approach

Tree BFS (Level-Order)

Use a queue to process the tree level by level. At each level, process all nodes in the queue, then add their children. Track the level size to know when one level ends and the next begins.

When to use

Level-order traversal, level-based aggregation, right/left side view.

---

Solutions

Solution 1: C# (Best: 460 ms)

Metric	Value
Runtime	460 ms
Memory	34.3 MB
Date	2020-01-26

Solution

/*
// Definition for a Node.
public class Node {
    public int val;
    public IList<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, IList<Node> _children) {
        val = _val;
        children = _children;
    }
}
*/
public class Solution {
    public IList<IList<int>> LevelOrder(Node root) {
        Queue<Node> q = new Queue<Node>();
        List<IList<int>> result = new List<IList<int>>();
        if(root == null) return result;
        q.Enqueue(root);
        while(q.Count!=0)
        {
            int levelCount = q.Count;
            List<int> curLevel = new List<int>();
            for (int i = 0; i < levelCount; i++)
            {
                var front = q.Dequeue();
                curLevel.Add(front.val);
                foreach (var child in front.children)
                {
                    q.Enqueue(child);
                }
            }
            result.Add(curLevel);
            
        }
        return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Tree Traversal	$O(n)$	$O(h)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.