N-ary Tree Level Order Traversal

medium tree bfs

Problem

Given the root of an N-ary tree, return the level-order traversal of its nodes' values as a list of lists.

Inputroot = [1, null, 3, 2, 4, null, 5, 6] // children-list format

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

Level 0 → [1]; Level 1 → children of 1; Level 2 → grandchildren in order.

tree (node:children1,children2,...; one per line)

from collections import deque

def level_order(root):
    if not root: return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            for child in node.children:
                q.append(child)
        res.append(level)
    return res

function levelOrder(root) {
  if (!root) return [];
  const res = [];
  let q = [root];
  while (q.length) {
    const level = [], next = [];
    for (const node of q) {
      level.push(node.val);
      for (const c of node.children) next.push(c);
    }
    res.push(level);
    q = next;
  }
  return res;
}

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<Node> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                Node node = q.poll();
                level.add(node.val);
                for (Node c : node.children) q.offer(c);
            }
            res.add(level);
        }
        return res;
    }
}

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

Explanation

To group an N-ary tree's nodes level by level, we use a breadth-first search (BFS) — but with a twist that lets us know exactly where one level ends and the next begins.

We keep a queue q of the nodes on the current level. The important detail is that at the start of each round we look at how many nodes are in the queue right now and process exactly that many. Everything currently queued belongs to the same level.

As we visit each node in this level we record its value into a fresh level list, and we push all of that node's children (it can have any number) into the queue for the next round. When the level finishes, we append level to the result.

Example: starting from root 1, level 0 is [1]. Its children 3, 2, 4 form level 1. Then the children of those, 5, 6, form level 2. The output is [[1], [3, 2, 4], [5, 6]].

Because every node enters and leaves the queue exactly once, we touch each node a single time while still keeping levels neatly separated.

Time: O(n) Space: O(w) — w = max level width