Skip to content

Volume ITechnology

4.14.8 — Binary Tree Level Order Traversal ​

LeetCode 102 · Medium · ★ Blind 75

The problem ​

Return the node values level by level, top to bottom, left to right within each level.

     3
   /   \
  9    20        →  [[3], [9, 20], [15, 7]]
      /   \
     15     7

To put this in plain English: you need to slice the tree horizontally. For each horizontal slice (level), give me a list of the numbers from left to right. Then give me a list containing all those level-lists.

Constraints to Keep in Mind: ​

  • 0 <= Number of nodes in the tree <= 2000
  • -1000 <= Node.val <= 1000
  • The tree might be empty (root is null).

The brute force, and where it wastes work ​

The naive way to get nodes level by level without a queue would be to run a DFS search multiple times.

  • How it works: You run DFS to find all nodes at depth 0. Then you run DFS again from the root to find all nodes at depth 1. Then you run DFS again to find all nodes at depth 2, and so on, until a DFS finds nothing.
  • Why it's too slow: Finding the nodes at depth d requires traversing all nodes above them. You end up visiting the top nodes many times. This takes O(n^2) time on a degenerate tree. To visit each node exactly once, we need to process the tree level by level in a single pass using Breadth-First Search (BFS).

The pattern ​

Any problem that says level, layer, row, or shortest number of steps is breadth-first search. A queue holds the frontier: take a node off the front, put its children on the back.

The one thing that needs care is knowing where one level ends and the next begins, since the queue mixes them.

The fix is one line: capture the queue's length before processing, and loop exactly that many times.

python
for _ in range(len(queue)):

At the top of each round, the queue holds exactly one complete level. Freezing that count means the children you add during the round belong to the next level and are not touched until the next round.

This line is the template for five problems in this chapter. Get it into muscle memory.

The solution ​

python
from collections import deque

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

        result = []
        queue = deque([root])                  # (2)

        while queue:                           # (3)
            level = []
            for _ in range(len(queue)):        # (4) exactly this level
                node = queue.popleft()         # (5)
                level.append(node.val)
                if node.left:                  # (6)
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)               # (7)

        return result
ts
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];                        // (1)

  const result: number[][] = [];
  let queue: TreeNode[] = [root];              // (2)

  while (queue.length) {                       // (3)
    const level: number[] = [];
    const next: TreeNode[] = [];               // (4) the next level, built separately
    for (const node of queue) {                // (5)
      level.push(node.val);
      if (node.left) next.push(node.left);     // (6)
      if (node.right) next.push(node.right);
    }
    result.push(level);                        // (7)
    queue = next;                              // swap in the next level
  }

  return result;
}

Line by line ​

(1) An empty tree has no levels, so the answer is an empty list.

(2) The queue starts with just the root. A queue is a line where items leave in the order they joined, first in, first out. Python's deque (pronounced "deck") removes from the front in constant time. At this moment the queue holds exactly level 0.

(3) One turn of this loop handles one whole level.

(4) Freeze the size of this level. len(queue) is measured once, before the inner loop starts. At that moment the queue holds exactly the nodes of the current level, so the inner loop runs exactly that many times. Children added during the loop belong to the next level and wait for the next turn. This one line is the whole trick for telling levels apart.

TypeScript sidesteps the same problem a different way. It builds the next level in a separate array, next, and swaps it in at the end. That also avoids shift(), which is slow on JavaScript arrays because every remaining item moves down one place.

(5) Take the next node of this level and record its value.

(6) Queue its children, left before right, so the next level comes out in left-to-right order. Only real children are added. Adding missing ones would fill the queue with Nones that later need filtering.

(7) The level is finished. Save it.

Hand Trace ​

Trace on the example tree:

  • Initial: queue = [3], result = []

Round 1:

  • len(queue) = 1. level = [].
  • Pop 3. level = [3]. Enqueue its children: 9, 20. queue = [9, 20].
  • Loop ends. result = [[3]].

Round 2:

  • len(queue) = 2. level = [].
  • Pop 9. level = [9]. No children. queue = [20].
  • Pop 20. level = [9, 20]. Enqueue children: 15, 7. queue = [15, 7].
  • Loop ends. result = [[3], [9, 20]].

Round 3:

  • len(queue) = 2. level = [].
  • Pop 15. level = [15]. No children. queue = [7].
  • Pop 7. level = [15, 7]. No children. queue = [].
  • Loop ends. result = [[3], [9, 20], [15, 7]].

queue is now empty, while loop terminates. Return result. ✓

Use a real queue. In Python, collections.deque removes from the front in O(1). A list with pop(0) is O(n) and turns this into a quadratic solution. JavaScript's Array.shift() has the same problem, which is why the TypeScript version builds the next level as a separate array and swaps — a common and clean way to sidestep it entirely.

Push children only if they exist, or the queue fills with nulls that must be filtered later.

Complexity ​

  • Time Complexity: O(n). We enqueue each of the n nodes exactly once, and we dequeue each node exactly once. Doing O(1) work per node gives O(n) total time.
  • Space Complexity: O(w) extra space, where w is the maximum width of the tree. For a balanced binary tree, the last level holds \lceil n/2 \rceil nodes, so w \approx n/2. Thus, space is O(n). BFS uses more memory than DFS on a balanced tree (O(n) against O(\log n)), and less on a degenerate one. That trade is why both traversals exist.

Edge cases ​

  • Empty tree. Line (1) returns [].
  • One node. One level: [[value]].
  • A tree shaped like a line. Every level holds one node, so the answer is a list of one-item lists, and the queue never holds more than one node.
  • A complete tree. The bottom level holds about half the nodes, so the queue grows to about n/2.

The five problems this template solves ​

Change what you do inside the level loop and you have solved:

problemchange
Level Ordercollect all values — this page
Right Side Viewkeep only the last value of each level — 4.14.9
Average of Levelssum and divide by the level size
Zigzag Level Orderreverse the list on alternate levels
Minimum Depthreturn the level number at the first leaf you meet

Minimum Depth deserves a closer look. BFS finds it faster than DFS, because it can stop at the first leaf, while DFS has to explore everything. Whenever "shortest" or "fewest" appears, BFS is usually the right tool. That becomes the whole argument for BFS in graphs in 4.20.

Doing it with DFS instead ​

You can produce level order with a depth-first walk, by passing the depth down and appending into the right bucket:

python
def levelOrder(self, root):
    result = []
    def dfs(node, depth):
        if not node: return
        if depth == len(result):
            result.append([])          # first node seen at this depth
        result[depth].append(node.val)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
    dfs(root, 0)
    return result

It works, it is O(n), and it uses O(h) space instead of O(w). Use it if asked "can you do it without a queue". Note that it cannot stop early the way BFS can.

What the interviewer will push on ​

"How do you know where a level ends?" The frozen len(queue) at the top of each round.

"Why deque and not a list?" pop(0) is O(n).

"Which uses more memory, BFS or DFS?" BFS is O(w) and DFS is O(h). On a balanced tree BFS is worse; on a degenerate tree DFS is worse.

"Can you do it depth-first?" Yes, by indexing into the result by depth.

"What if the tree is enormous and you only need the first few levels?" BFS stops naturally; DFS would have to be depth-limited.

One thing to volunteer: name the frozen-length line as the level-boundary trick before writing it. Everything else in this problem is routine.

Next: 4.14.9 Binary Tree Right Side View — the same loop with one line changed.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet