ToolMight LogoToolMight
MediumTrees & BSTPattern: Breadth-First Search (BFS)Pattern: Queue Level Batching

Binary Tree Level Order Traversal

Return the level order traversal of a binary tree's node values from left to right, level by level. The premier problem for learning FIFO queue BFS level snapshots.

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Examples & Constraints

Example 1
Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]
Explanation: Level 0 has node 3. Level 1 has nodes 9 and 20. Level 2 has nodes 15 and 7.
Example 2
Input: root = []
Output: []
Explanation: Empty tree produces an empty list.
Constraints
  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000

BFS with Queue Level Size Snapshot

Optimal Approach
Time:O(n)
Space:O(w)

Use a FIFO queue. At each level, record the queue size and drain exactly that many nodes into a level list while enqueuing their children in O(n) time.

Time ComplexityO(n)

Every node in the tree of size N is enqueued and dequeued exactly once.

Space ComplexityO(w)

Consumes memory proportional to the maximum breadth W of the tree stored in the queue (at most N/2 nodes for a full balanced binary tree).

Underlying algorithmic logic

The Core Mental Model: Level-by-Level Flushing

Standard Breadth-First Search (BFS) processes nodes in order of distance from the root using a queue. But how do we know which nodes belong to which level?

The key insight is the Queue Size Snapshot:

  1. If the tree is empty (root == null), return an empty list [].
  2. Push root into a FIFO queue.
  3. While the queue is not empty:
  • Capture levelSize = queue.size(). This is the exact number of nodes that belong exclusively to the current horizontal level!
  • Create an empty list currentLevel.
  • Loop exactly levelSize times:
  • Pop a node curr = queue.pop().
  • Append curr.val to currentLevel.
  • If curr.left exists, push it into the queue.
  • If curr.right exists, push it into the queue.
  • Append currentLevel to the final result list res.
  1. When the queue is empty, return res.

Why the Queue Size Snapshot Guarantees Isolation

Even though child nodes for the next level are being pushed into the queue during the loop, our loop only runs levelSize times (which was measured before any children were pushed). This guarantees complete separation between consecutive horizontal tiers!

Step-by-step execution walkthrough

1
Level 0 (Root)

Queue contains [3]. levelSize = 1. Pop 3. Push children 9 and 20. level = [3].

res = [[3]], queue = [9, 20]
2
Level 1 (Children of Root)

Queue contains [9, 20]. levelSize = 2. Pop 9 (no children). Pop 20 (push 15, 7). level = [9, 20].

res = [[3], [9, 20]], queue = [15, 7]
3
Level 2 (Leaves)

Queue contains [15, 7]. levelSize = 2. Pop 15 and 7 (no children). level = [15, 7].

res = [[3], [9, 20], [15, 7]], queue = []
4
Queue Empty

Queue is empty. Traversal terminates cleanly.

Final result: [[3], [9, 20], [15, 7]]
Advantages
  • •Optimal linear O(n) runtime
  • •Clean level isolation using queue.size() without extra level counters
Trade-offs
  • •Consumes queue memory proportional to the widest level of the tree

Code Implementations

Copy & paste production-ready solutions for BFS with Queue Level Size Snapshot in your language of choice

File: solution.py
Python
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    res = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(current_level)
    return res
if __name__ == "__main__":
    # Tree: [3, 9, 20, null, null, 15, 7]
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print("Level Order:", level_order(root))
Interactive visualizer available

Understand Tree Traversals Visually

Observe recursive visiting orders (Inorder, Preorder, Postorder) over node trees. Test live edge cases and watch memory state transitions step-by-step.

Launch Tree Traversals Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyTrees & BST
Visualizer

Maximum Depth of Binary Tree

Find the maximum depth (height) of a binary tree along the longest path from root to leaf. The quintessential problem for learning bottom-up divide-and-conquer tree recursion.

1 approach(O(n))
Learn logic
EasyTrees & BST
Visualizer

Invert Binary Tree

Mirror-flip a binary tree so every left subtree swaps with the right subtree. The quintessential problem for mastering tree recursion and depth-first traversal.

1 approach(O(n))
Learn logic
EasyTrees & BST
Visualizer

Subtree of Another Tree

Determine if a binary tree contains a subtree identical in structure and node values to another tree. Learn how to combine outer tree DFS traversal with inner tree isomorphism matching.

1 approach(O(n * m))
Learn logic