Dump binary tree levels as a nested list

You're in a technical interview at Amazon, and the interviewer draws a binary tree on the whiteboard. "I want you to collect the values at each level into separate lists," they say. "So the root goes into one list, its children into another, and so on." This is binary tree level order traversal, also known as "Binary Tree Level Order Traversal" on other platforms. It's a bread-and-butter BFS problem that shows up constantly at companies like Amazon and Salesforce, and it forms the basis for a whole family of tree problems.

TL;DR

Use BFS with a queue. Enqueue the root, then repeatedly drain the queue one level at a time: capture the queue's size, process exactly that many nodes (adding their values to a level list and enqueueing their children), then append the level list to the result. This runs in O(n) time and O(n) space. The key insight is snapshotting queue.size() before the inner loop so you know exactly where one level ends and the next begins.

Why This Problem Matters

Level order traversal is the canonical BFS problem for trees. Once you internalize this pattern, you can solve a dozen related problems with minor tweaks: zigzag traversal, right-side view, maximum width, average per level, and more. Interviewers at Amazon and Salesforce love it because it tests both your understanding of tree structure and your ability to work with queues.

Binary Trees and BFS: A Quick Refresher

A binary tree is a hierarchical structure where each node has at most two children. Unlike DFS approaches (pre-order, in-order, post-order) that dive deep before backtracking, BFS explores the tree horizontally, visiting all nodes at one depth before moving deeper.

In the tree above, BFS would visit nodes in the order 1, 2, 3, 4, 5. That's left to right, level by level.

Understanding the Problem

Given: The root of a binary tree Task: Collect node values level by level into a nested list Return: A list of lists, where each inner list contains the values at that level

Here's what the output looks like for our example tree:

• Level 0 contains just the root: [1]
• Level 1 contains its children: [2, 3]
• Level 2 contains the grandchildren: [4, 5]

So the final result is [[1], [2, 3], [4, 5]].

Edge Cases

1. Empty tree (null root): Return an empty list []
2. Single node: Return [[rootValue]]
3. Skewed tree (all nodes on one side): Each level has exactly one node
4. Complete tree: The last level can have up to half of all nodes

Solution Approach

The core idea is straightforward: use a queue to process nodes level by level. But the tricky part is knowing when one level ends and the next begins. You can't just blindly dequeue and assume everything in the queue is at the same depth.

The Level-Size Trick

Here's the key insight that makes this problem clean. Before you start processing any node at a given level, check how many nodes are currently in the queue. That number is exactly the count of nodes at the current level. Process that many nodes (and no more), enqueueing their children as you go. When you've processed all of them, everything remaining in the queue belongs to the next level.

Let me trace through our example tree to show how this works:

Level 0 processing: Queue starts with [1]. Size is 1, so process 1 node. Dequeue node 1, add value to level list. Enqueue its children 2 and 3. Level list: [1].

Level 1 processing: Queue is [2, 3]. Size is 2, so process 2 nodes. Dequeue node 2 (no children), dequeue node 3 (children 4 and 5 get enqueued). Level list: [2, 3].

Level 2 processing: Queue is [4, 5]. Size is 2, so process 2 nodes. Dequeue node 4 (no children), dequeue node 5 (no children). Level list: [4, 5].

Queue is now empty. Result: [[1], [2, 3], [4, 5]].

Visualizing BFS Traversal

Watch how BFS processes the tree node by node:

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public List<List<Integer>> dumpTree(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();

    if (root == null) return result;

    Deque<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
      int levelSize = queue.size();
      List<Integer> currentLevel = new ArrayList<>();

      for (int i = 0; i < levelSize; i++) {
        TreeNode node = queue.poll();
        currentLevel.add(node.data);

        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
      }

      result.add(currentLevel);
    }

    return result;
  }
}

Let's walk through the critical parts of this code:

1. Null check: If the root is null, there are no levels to collect, so return an empty list immediately.

2. Queue initialization: We add the root to the queue to kick off the BFS. Java's Deque interface with LinkedList gives us O(1) enqueue and dequeue operations via offer() and poll().

3. The outer while loop: Each iteration processes one complete level. It runs until the queue is empty, meaning we've visited every reachable node.

4. The level-size snapshot: int levelSize = queue.size() captures how many nodes are at the current level before we start processing them. This is the line that makes the whole approach work.

5. The inner for loop: Processes exactly levelSize nodes. For each node, we record its value and enqueue its non-null children. Children go to the back of the queue, so they won't be processed until the next iteration of the outer loop.

6. Collecting the level: After the inner loop finishes, currentLevel contains all values for that level, and we add it to the result.

Another Example: A Balanced Tree

Let's verify our understanding with a fuller tree:

For this tree, the algorithm produces [[1], [2, 3], [4, 5, 6, 7]]. Each level doubles in size, and the queue peaks at 4 nodes when processing level 2.

Complexity Analysis

Time Complexity: O(n)

Every node is enqueued once and dequeued once. Both operations are O(1) with a proper queue. We also do O(1) work per node (adding to the level list, checking children). Total work is proportional to the number of nodes.

Space Complexity: O(n)

The space usage comes from two sources:

• The queue: At any point, it holds at most one full level of nodes. In a complete binary tree, the widest level (the last one) has roughly n/2 nodes. That's O(n).
• The result list: Stores every node's value exactly once, which is O(n).

The queue dominates in terms of auxiliary space, and it scales with the width of the tree rather than its height. Compare this to DFS, where stack space scales with the tree's height.

Common Pitfalls

These are the most common mistakes with this problem:

1. Forgetting the level-size snapshot: If you don't capture queue.size() before the inner loop, you'll process children from the current level as if they belong to it. The queue grows during iteration, and without the snapshot, you lose track of level boundaries.

   // Wrong - queue.size() changes as you enqueue children
   for (int i = 0; i < queue.size(); i++) { ... }
   
   // Correct - capture size before processing
   int levelSize = queue.size();
   for (int i = 0; i < levelSize; i++) { ... }
   

2. Using a stack instead of a queue: A stack gives you DFS, not BFS. You need FIFO ordering to process nodes left to right, level by level.

3. Not handling the null root: Enqueueing a null root and then trying to access its children causes a NullPointerException.

4. Using ArrayList as a queue: Removing from the front of an ArrayList is O(n) because it shifts all remaining elements. Use LinkedList or ArrayDeque for O(1) dequeue operations.

Interview Tips

When tackling this problem in an interview:

1. Clarify the output format: "Should I return a list of lists, or print the values?" Some variations ask for a flat list or comma-separated output per level.

2. Draw the tree and trace the queue: Sketch the example tree, then show the queue state at each step. This demonstrates clear thinking and catches bugs before you code.

3. Mention the level-size trick explicitly: Say something like, "I'll capture the queue's size at the start of each level so I know exactly how many nodes to process." This shows you understand the non-obvious part of the algorithm.

4. Discuss BFS vs DFS trade-offs: "BFS is natural here because we need level-by-level grouping. DFS would require tracking depths separately." This shows breadth of knowledge.

5. Know the follow-ups: Interviewers often ask variations like zigzag level order, bottom-up level order, or right-side view. All of these are minor modifications to this template.

Key Takeaways

• The level-size snapshot (int levelSize = queue.size()) before the inner loop is what separates levels in BFS. Without it, you can't tell where one level ends and the next begins.
• BFS with a queue gives O(n) time and O(n) space, both of which are optimal for this problem since you must visit every node and store every value.
• This BFS template is reusable: zigzag traversal, bottom-up order, right-side view, and level averages all build on the same queue-based pattern with small modifications.
• Always use a proper queue (LinkedList or ArrayDeque in Java, deque in Python) rather than an ArrayList or plain array to avoid O(n) dequeue overhead.
• Handle the null root edge case first. It simplifies the rest of the code and prevents null pointer errors.

Solutions in Other Languages

Python

from collections import deque

class Solution:
    def dump_tree(self, root):
        result = []
        if root is None:
            return result

        queue = deque()
        queue.append(root)

        while queue:
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.data)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            result.append(current_level)

        return result

Python's collections.deque provides O(1) popleft(), making it the right choice over a plain list where pop(0) is O(n).

JavaScript

class Solution {
  dumpTree(root) {
    const result = [];
    if (root === null) return result;

    const queue = new Queue();
    queue.enqueue(root);

    while (queue.nonEmpty()) {
      const levelSize = queue.length;
      const currentLevel = [];

      for (let i = 0; i < levelSize; i++) {
        const node = queue.dequeue();
        currentLevel.push(node.data);

        if (node.left !== null) queue.enqueue(node.left);
        if (node.right !== null) queue.enqueue(node.right);
      }

      result.push(currentLevel);
    }

    return result;
  }
}

TypeScript

class Solution {
  dumpTree(root: TreeNode | null): number[][] {
    const result: number[][] = [];
    if (root === null) return result;

    let currentLevel = new Queue<TreeNode>(),
      nextLevel = new Queue<TreeNode>();
    currentLevel.offer(root);
    let currentLevelData: number[] = [];

    while (!currentLevel.isEmpty()) {
      const node = currentLevel.poll()!;
      currentLevelData.push(node.data);

      if (node.left !== null) nextLevel.offer(node.left);
      if (node.right !== null) nextLevel.offer(node.right);

      if (currentLevel.isEmpty()) {
        result.push(currentLevelData);
        currentLevelData = [];
        currentLevel = nextLevel;
        nextLevel = new Queue<TreeNode>();
      }
    }

    return result;
  }
}

The TypeScript solution uses a two-queue approach: one for the current level and one for the next. When the current queue empties, swap them. Both approaches produce the same result.

C++

#include <deque>
#include <vector>

class Solution {
public:
  std::vector<std::vector<int>> dumpTree(TreeNode *root) {
    std::vector<std::vector<int>> result;
    if (root == nullptr) return result;

    std::deque<TreeNode *> queue;
    queue.push_back(root);

    while (!queue.empty()) {
      int levelSize = queue.size();
      std::vector<int> currentLevel;

      for (int i = 0; i < levelSize; i++) {
        TreeNode *node = queue.front();
        queue.pop_front();
        currentLevel.push_back(node->data);

        if (node->left != nullptr) queue.push_back(node->left);
        if (node->right != nullptr) queue.push_back(node->right);
      }

      result.push_back(currentLevel);
    }

    return result;
  }
};

Go

func (s *Solution) DumpTree(root *TreeNode) [][]int {
    var result [][]int
    if root == nil {
        return result
    }

    queue := NewQueue()
    queue.Offer(root)

    for !queue.IsEmpty() {
        levelSize := queue.Size()
        currentLevel := make([]int, 0, levelSize)

        for i := 0; i < levelSize; i++ {
            node := queue.Poll().(*TreeNode)
            currentLevel = append(currentLevel, node.Data)

            if node.Left != nil {
                queue.Offer(node.Left)
            }
            if node.Right != nil {
                queue.Offer(node.Right)
            }
        }

        result = append(result, currentLevel)
    }

    return result
}

Scala

import scala.collection.mutable

class Solution {
  def dumpTree(root: TreeNode): List[List[Int]] = {
    val result = mutable.ArrayBuffer[List[Int]]()
    if (root == null) return result.toList

    val queue = mutable.Queue[TreeNode]()
    queue.enqueue(root)

    while (queue.nonEmpty) {
      val levelSize = queue.size
      val currentLevel = mutable.ArrayBuffer[Int]()

      for (_ <- 0 until levelSize) {
        val node = queue.dequeue
        currentLevel.append(node.data)

        if (node.left != null) queue.enqueue(node.left)
        if (node.right != null) queue.enqueue(node.right)
      }

      result.append(currentLevel.toList)
    }

    result.toList
  }
}

Kotlin

import java.util.ArrayDeque

class Solution {
    fun dumpTree(root: TreeNode?): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        if (root == null) return result

        val queue = ArrayDeque<TreeNode?>()
        queue.offer(root)

        while (queue.isNotEmpty()) {
            val levelSize = queue.size
            val currentLevel = mutableListOf<Int>()

            for (i in 0 until levelSize) {
                val node = queue.poll()!!
                currentLevel.add(node.data)

                if (node.left != null) queue.offer(node.left)
                if (node.right != null) queue.offer(node.right)
            }

            result.add(currentLevel)
        }

        return result
    }
}

Swift

func dumpTree(_ root: TreeNode?) -> [[Int]] {
    var result = [[Int]]()
    guard let root = root else { return result }

    var queue: [TreeNode] = [root]

    while !queue.isEmpty {
        let levelSize = queue.count
        var currentLevel = [Int]()

        for _ in 0..<levelSize {
            let node = queue.removeFirst()
            currentLevel.append(node.data)

            if let left = node.left { queue.append(left) }
            if let right = node.right { queue.append(right) }
        }

        result.append(currentLevel)
    }

    return result
}

Rust

use std::collections::VecDeque;

impl Solution {
    pub fn dump_tree(&self, root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        if root.is_none() { return result; }

        let mut queue: VecDeque<Box<TreeNode>> = VecDeque::new();
        queue.push_back(root.unwrap());

        while !queue.is_empty() {
            let level_size = queue.len();
            let mut current_level: Vec<i32> = Vec::new();

            for _ in 0..level_size {
                let node = queue.pop_front().unwrap();
                current_level.push(node.data);

                if let Some(left) = node.left { queue.push_back(left); }
                if let Some(right) = node.right { queue.push_back(right); }
            }

            result.push(current_level);
        }

        result
    }
}

Rust's ownership model means we move nodes out of the queue with pop_front() and move children in with push_back(). No reference counting or garbage collection needed.

C#

public class Solution {
    public List<List<int>> DumpTree(TreeNode? root) {
        var result = new List<List<int>>();
        if (root == null) return result;

        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        while (queue.Count > 0) {
            var levelSize = queue.Count;
            var currentLevel = new List<int>();

            for (int i = 0; i < levelSize; i++) {
                var node = queue.Dequeue();
                currentLevel.Add(node.data);

                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }

            result.Add(currentLevel);
        }

        return result;
    }
}

Dart

import 'dart:collection';

class Solution {
  List<List<int>> dumpTree(TreeNode? root) {
    List<List<int>> result = [];
    if (root == null) return result;

    Queue<TreeNode> queue = Queue();
    queue.add(root);

    while (queue.isNotEmpty) {
      int levelSize = queue.length;
      List<int> currentLevel = [];

      for (int i = 0; i < levelSize; i++) {
        TreeNode node = queue.removeFirst();
        currentLevel.add(node.data);

        if (node.left != null) queue.add(node.left!);
        if (node.right != null) queue.add(node.right!);
      }

      result.add(currentLevel);
    }

    return result;
  }
}

PHP

class Solution {
    public function dumpTree(?TreeNode $root): array {
        $result = [];
        if ($root === null) return $result;

        $queue = [$root];

        while (!empty($queue)) {
            $levelSize = count($queue);
            $currentLevel = [];

            for ($i = 0; $i < $levelSize; $i++) {
                $node = array_shift($queue);
                $currentLevel[] = $node->data;

                if ($node->left !== null) $queue[] = $node->left;
                if ($node->right !== null) $queue[] = $node->right;
            }

            $result[] = $currentLevel;
        }

        return $result;
    }
}

Ruby

class Solution
  def dump_tree(root)
    result = []
    return result if root.nil?

    queue = [root]

    until queue.empty?
      level_size = queue.size
      current_level = []

      level_size.times do
        node = queue.shift
        current_level.push(node.data)

        queue.push(node.left) if node.left
        queue.push(node.right) if node.right
      end

      result.push(current_level)
    end

    result
  end
end

Practice and Related Problems

Level order traversal is the gateway to a whole category of BFS tree problems. Once you've nailed this one, try these variations:

• Bottom-up level order traversal - Same BFS, but reverse the result at the end
• Binary tree right side view - Collect only the last node at each level
• Zigzag level order traversal - Alternate left-to-right and right-to-left per level
• Maximum width of binary tree - Track positions to find the widest level

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. The BFS template you've learned here will serve you well across dozens of tree and graph problems.