What is the brute force approach and complexity for Binary Tree Level Order Traversal?

For each depth d, walk the whole tree and keep the nodes at depth d with time complexity O(N · H) and space complexity O(H).

What is the optimal approach and complexity for Binary Tree Level Order Traversal?

Queue-based BFS; take size = q.size() at the start of each round and pop exactly that many with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Binary Tree Level Order Traversal?

Look for key signals in the prompt: "level by level" indicates Rows are depths. A question about rows is a breadth-first question, not a path question.; "left to right inside each level" indicates A queue gives this order for free, because children are pushed left, then right.; "return a list of lists" indicates One inner list per row, so the number of rounds equals the number of rows..

Binary Tree Level Order Traversal

Medium·LeetCode #102Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTree BFS, Level order (size snapshot per round)

Complexity:O(N · H)→O(N)

Key Insight

Use a queue, and split it into rounds. At the start of each round, take size = q.size() before pushing any children. Those size nodes are exactly one row. Pop that many, push their children to the back, and the next round starts with the next row.

Core Validity Invariant

The queue holds exactly one row when a round starts, so popping size nodes takes out that whole row and nothing from the row below it.

Problem

You are given the root of a binary tree. Return the node values one row at a time: first the root's row, then the row below it, and so on. Inside each row, read the nodes from left to right.

Each row becomes one inner list in the answer. An empty tree gives an empty answer.

Input

The root of a binary tree. It can be empty (null).

In the examples, a tree is written in level order: the root first, then each row left to right. A null marks a missing child, so [3, 9, 20, null, null, 15, 7] means 9 and 20 are the root's children, and 9 has no children.

Output

A list of rows. The first list is the root's row, the next list holds its children, and so on. Each row is read left to right.

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]

Output: [[3], [9, 20], [15, 7]]

Row 0 is 3. Row 1 is its children 9 and 20. Row 2 is 15 and 7, the children of 20 (9 has none).

Example 2

Input: root = [1]

Output: [[1]]

A single node is one row.

Example 3

Input: root = []

Output: []

No nodes, so no rows.

Constraints

• The number of nodes in the tree is in the range [0, 2000].
• −1000 ≤ Node.val ≤ 1000

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Is a row of the tree a set of nodes at the same depth? What order would I need to visit nodes in to print one row at a time?
2.
Does depth-first search naturally visit the nodes row by row, or does breadth-first search?
3.
If I visit a node and then its children, how would I know where one row stops and the next row starts?
4.
Could I walk the whole tree once for each row and keep only the nodes at that depth? What would that cost?
5.
When one row is about to start, how many nodes belong to it? Can I know that before I pop any of them?

Brute force approach

Idea

Find the tree's height H. For each depth d from 0 to H − 1, walk the whole tree and collect the nodes whose depth is exactly d. Each walk gives one row, already left to right.

Thinking process

1
A row is the set of nodes at one depth. So if I can ask 'what is at depth d?', I can build the answer one row at a time.
2
The height is the number of rows. On [3, 9, 20, null, null, 15, 7] the height is 3, so there are 3 rows to collect.
3
Walk for depth 0 keeps only 3, so the row is [3]. Walk for depth 1 keeps 9 and 20, so [9, 20]. Walk for depth 2 keeps 15 and 7, so [15, 7].
4
Each walk visits all 5 nodes, even when it only wants one or two of them. Three walks cost 15 node visits.

Visual

Each walk goes through the whole tree. Green = kept for this row, grey = visited but at the wrong depth, blue = visited now.

One full walk per rowroot = [3, 9, 20, null, null, 15, 7]step 1/19

row 0

Walk

walk for depth: 0
this walk: visit 1 of 5
node visits so far (all walks): 1

rows so far

[ ]

depth 0 = 0: keep 3

Walk 0 visits 3. It is at depth 0, so it goes into row 0.

Code & Implementation

brute.cpp

class Solution {
    // Walks the whole tree and collects every node at depth `target`.
    void collect(TreeNode* node, int depth, int target, vector<int>& out) {
        if (!node) return;
        if (depth == target) out.push_back(node->val);
        collect(node->left, depth + 1, target, out);
        collect(node->right, depth + 1, target, out);
    }

    int height(TreeNode* node) {
        if (!node) return 0;
        return 1 + max(height(node->left), height(node->right));
    }

public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> levels;
        int h = height(root);

        // One full walk of the tree for every depth.
        for (int d = 0; d < h; d++) {
            vector<int> level;
            collect(root, 0, d, level);
            levels.push_back(level);
        }
        return levels;
    }
};

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // Walks the whole tree and collects every node at depth `target`.
    private void collect(TreeNode node, int depth, int target, List<Integer> out) {
        if (node == null) return;
        if (depth == target) out.add(node.val);
        collect(node.left, depth + 1, target, out);
        collect(node.right, depth + 1, target, out);
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        int h = height(root);

        // One full walk of the tree for every depth.
        for (int d = 0; d < h; d++) {
            List<Integer> level = new ArrayList<>();
            collect(root, 0, d, level);
            levels.add(level);
        }
        return levels;
    }
}

from typing import Optional, List
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # Walks the whole tree and collects every node at depth `target`.
        def collect(node: Optional[TreeNode], depth: int, target: int, out: List[int]) -> None:
            if not node:
                return
            if depth == target:
                out.append(node.val)
            collect(node.left, depth + 1, target, out)
            collect(node.right, depth + 1, target, out)

        def height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            return 1 + max(height(node.left), height(node.right))

        levels: List[List[int]] = []
        h = height(root)

        # One full walk of the tree for every depth.
        for d in range(h):
            level: List[int] = []
            collect(root, 0, d, level)
            levels.append(level)
        return levels

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

// Walks the whole tree and collects every node at depth `target`.
function collect(node: TreeNode | null, depth: number, target: number, out: number[]): void {
    if (!node) return;
    if (depth === target) out.push(node.val);
    collect(node.left, depth + 1, target, out);
    collect(node.right, depth + 1, target, out);
}

function height(node: TreeNode | null): number {
    if (!node) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

export function levelOrder(root: TreeNode | null): number[][] {
    const levels: number[][] = [];
    const h = height(root);

    // One full walk of the tree for every depth.
    for (let d = 0; d < h; d++) {
        const level: number[] = [];
        collect(root, 0, d, level);
        levels.push(level);
    }
    return levels;
}

Complexity

Time O(N · H)Space O(H)

Each of the H rows costs one full walk over all N nodes. On a chain of 2000 nodes that is about 4 million visits. The recursion only goes H deep, so the extra space is O(H). The optimal visits every node exactly once.

Optimized approach

Idea

Start from brute force

The brute force walks the whole tree once for every row. Each walk asks 'which nodes are at depth d?' and throws away everything else.

Find the repeated work

Every walk goes through the whole tree again. A node at depth 5 is visited once for each of the H rows, even though it only belongs to one of them. BFS visits each node once, when its own row comes up.

Define the state — what variables do I need?

queue: Nodes waiting to be visited, in left-to-right order. At the start of a round it holds exactly one row.
size: How many nodes are in this round's row. Taken once, before any child is pushed.
level: The values popped so far in this round, left to right.
levels: The answer so far: one finished list per round.

Define validity

The queue holds exactly one row when a round starts, so popping size nodes takes out that whole row and nothing from the row below it.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

If root is not null: queue = [root]

Row 0 is the root alone.

Start of each round

size = queue.size()

These size nodes are this row. The children of this row have not been pushed yet, because they are only pushed while this row is being popped.

Each of the `size` pops

pop the front, add its value to level, push left, then right

Children go to the back of the queue, so they wait for the next round. They are never mixed into this row.

End of the round

levels.push_back(level)

All size nodes of the row were popped, so the row is complete.

What does the current window add to the answer?

Each round adds exactly one list to levels, and that list holds every node of one depth, left to right.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> levels;
        if (!root) return levels;

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            // The queue holds exactly one row now. Take its size BEFORE
            // pushing any children, so the next row is not counted.
            int size = q.size();
            vector<int> level;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);     // belongs to the next row
                if (node->right) q.push(node->right);   // belongs to the next row
            }
            levels.push_back(level);
        }
        return levels;
    }
};

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            // The queue holds exactly one row now. Take its size BEFORE
            // pushing any children, so the next row is not counted.
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.offer(node.left);     // belongs to the next row
                if (node.right != null) q.offer(node.right);   // belongs to the next row
            }
            levels.add(level);
        }
        return levels;
    }
}

from typing import Optional, List
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        levels: List[List[int]] = []
        if not root:
            return levels

        q: deque[TreeNode] = deque([root])
        while q:
            # The queue holds exactly one row now. Take its size BEFORE
            # pushing any children, so the next row is not counted.
            size = len(q)
            level: List[int] = []
            for _ in range(size):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)     # belongs to the next row
                if node.right:
                    q.append(node.right)    # belongs to the next row
            levels.append(level)
        return levels

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

export function levelOrder(root: TreeNode | null): number[][] {
    const levels: number[][] = [];
    if (!root) return levels;

    const q: TreeNode[] = [root];
    while (q.length > 0) {
        // The queue holds exactly one row now. Take its size BEFORE
        // pushing any children, so the next row is not counted.
        const size = q.length;
        const level: number[] = [];
        for (let i = 0; i < size; i++) {
            const node = q.shift()!;
            level.push(node.val);
            if (node.left) q.push(node.left);     // belongs to the next row
            if (node.right) q.push(node.right);   // belongs to the next row
        }
        levels.push(level);
    }
    return levels;
}

Complexity

Time O(N)Space O(N)

Each node is pushed once and popped once. The queue holds at most one row plus its children, so it is at most about N nodes wide. The output itself is O(N).

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each depth d, walk the whole tree and keep the nodes at depth d	O(N · H)	O(H)
Optimal	Queue-based BFS; take size = q.size() at the start of each round and pop exactly that many	O(N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“level by level”Rows are depths. A question about rows is a breadth-first question, not a path question.
“left to right inside each level”A queue gives this order for free, because children are pushed left, then right.
“return a list of lists”One inner list per row, so the number of rounds equals the number of rows.

Tree grouped by depth+queue (FIFO) BFS+one round = one snapshot of the queue size→Tree BFS, Level order (size snapshot per round)

The question asks for rows, not paths, so Tree BFS is the right family. The key rule is take size at the start of each round and pop exactly that many. The row below always sits behind the current row in the queue, so the snapshot is the only thing that marks the boundary. Binary Tree Level Order II, N-ary Level Order and Zigzag all reuse this same loop.

Don't make this mistake

Reading `q.size()` inside the loop condition

✗ for (int i = 0; i < q.size(); i++) {

✓ int size = q.size(); for (int i = 0; i < size; i++) {

Pattern confusion: the loop condition is checked after every pop, and each pop can push two children. The queue grows with the row below, so the loop keeps going past this row's boundary and the next row bleeds into this one. On [3, 9, 20, null, null, 15, 7] the live version gives [[3, 9], [20, 15], [7]]. After 3 is popped, the queue holds [9, 20] (size 2), so the loop also pops 9 and files it under row 0.

Pushing null children

✗ q.push(node->left); q.push(node->right);

✓ if (node->left) q.push(node->left); if (node->right) q.push(node->right);

A null pointer goes into the queue, and the next pop reads ->val of nullptr and crashes. Node 9 in the example has no children, so the wrong version queues two nulls right behind 20.

Forgetting the empty tree

✗ queue<TreeNode*> q; q.push(root);

✓ if (!root) return levels; queue<TreeNode*> q; q.push(root);

An empty tree must return []. Without the check, a null root sits in the queue and crashes on its first pop.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree BFS translate into production architectures and low-level memory mechanics.

LLD Architecture