Level Order Traversal
EasyA queue, one level per pass
Problem
Return the level-order (breadth-first) traversal of a binary tree, one list per level.
Use a queue: visit a level, enqueue its children, then move to the next level.
The idea
Push the root, then repeatedly take the queue's current size and pop exactly that many nodes — those form one level — pushing their children as you go. The size snapshot is what separates the levels.
The trick
- Snapshot the queue size before the inner loop.
- Children pushed during a pass belong to the next level.
- O(n) time, O(width) space.
Step 1 of 5. Level-order BFS: snapshot the queue size to process exactly one level per iteration.
Fix the level width up front.
1const q = [root], out = [];2while (q.length) {3 const level = [];4 for (let n = q.length; n > 0; n--) {5 const node = q.shift();6 level.push(node.val);7 if (node.left) q.push(node.left);8 if (node.right) q.push(node.right);9 }10 out.push(level);11}Input
- nodes
- 6, 5 edges
Memory
- levels
- —
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [3,9,20,null,null,15,7]
- Output:
- [[3],[9,20],[15,7]]
- Explanation:
- Read the tree level by level, top to bottom.
Example 2
- Input:
- tree = [1]
- Output:
- [[1]]
- Explanation:
- One node, one level.
Example 3
- Input:
- tree = []
- Output:
- []
- Explanation:
- Nothing to visit.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.