Binary Tree Level Order
MediumProcess one whole level per iteration
Visit the tree one level at a time, top to bottom, using a queue.
The idea
Snapshot the queue size at the start of each loop — that's exactly one level. Drain that many nodes, collecting their values and enqueuing their children for the next level.
Step 1 of 5. Level-order BFS: snapshot the queue size to process exactly one level per iteration.
1/5
Optimal
timeO(n)spaceO(n)
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.