N-ary Tree Level Order Traversal

Problem

Given an N-ary tree, return its level-order traversal as a list of lists.

Key insight: BFS with queue. Unlike binary tree, iterate over node.children instead of fixed left/right.

Solutions

// C++
vector<vector<int>> levelOrder(Node* root) {
    if (!root) return {};
    vector<vector<int>> res;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        res.push_back({});
        while (sz--) {
            auto node = q.front(); q.pop();
            res.back().push_back(node->val);
            for (auto child : node->children) q.push(child);
        }
    }
    return res;
}

// Java
public List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        List<Integer> level = new ArrayList<>();
        while (sz-- > 0) {
            Node node = q.poll();
            level.add(node.val);
            q.addAll(node.children);
        }
        res.add(level);
    }
    return res;
}

// JavaScript
function levelOrder(root) {
    if (!root) return [];
    const res = [];
    let queue = [root];
    while (queue.length) {
        res.push(queue.map(n => n.val));
        queue = queue.flatMap(n => n.children);
    }
    return res;
}

# Python
from collections import deque

def levelOrder(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            q.extend(node.children)
        result.append(level)
    return result

Complexity

Time: O(n)
Space: O(n)