N-ary Tree Level Order Traversal
Medium · Graphs · Explanation and code example
Breadth-First Search
How it works
Use a queue to visit an N-ary tree one level at a time. The queue length at the start of a level tells how many nodes belong to that level. Append each node’s children in order, then begin the next level.
Steps
- Return [] for an empty root.
- Process the current queue length and collect node values.
- Enqueue children and append the finished level.
Complexity
- Time: O(n).
- Space: O(n) including the queue and output.
Things to watch for
- Each node can have any number of children.
- Capture the level size before enqueueing children.
- Preserve the given child order.
Python code example
import collections
class Solution:
def levelOrder(self, root: 'Node') -> list[list[int]]:
if not root:
return []
ans = []
q = collections.deque([root])
while q:
currLevel = []
for _ in range(len(q)):
node = q.popleft()
currLevel.append(node.val)
for child in node.children:
q.append(child)
ans.append(currLevel)
return ans
C++ code example
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
if (root == nullptr)
return {};
vector<vector<int>> ans;
queue<Node*> q{{root}};
while (!q.empty()) {
vector<int> currLevel;
for (int sz = q.size(); sz > 0; --sz) {
Node* node = q.front();
q.pop();
currLevel.push_back(node->val);
for (Node* child : node->children)
q.push(child);
}
ans.push_back(currLevel);
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.