Level order traversal of a binary tree

You're twenty minutes into an Amazon interview when the interviewer sketches a binary tree on the whiteboard and asks, "How would you print every node, one level at a time?" This question, also known as Binary Tree Level Order Traversal on other platforms, is testing something specific: whether you understand breadth-first search and know when to reach for a queue instead of recursion. It shows up constantly in interviews because BFS is the backbone of shortest-path algorithms, network protocols, and dozens of graph problems you will face later in the round.

TL;DR

Use a queue. Start by enqueuing the root, then loop: dequeue a node, record its value, and enqueue its non-null children. The queue's FIFO property guarantees that every node at depth d is processed before any node at depth d+1. This runs in O(n) time and O(n) space.

Why This Problem Matters

Level order traversal is the canonical introduction to BFS on trees. Most candidates learn trees through recursive DFS first, so this problem forces a gear shift: you need an iterative approach driven by a queue. That skill transfers directly to graph BFS, shortest-path problems, and multi-source search, all of which are standard fare at companies like Amazon, Meta, and Google.

Binary Trees and Traversal Orders

A binary tree is a hierarchical structure where each node has at most two children. There are several ways to visit every node, and each produces a different ordering:

• Preorder (DFS): root, left subtree, right subtree
• Inorder (DFS): left subtree, root, right subtree
• Postorder (DFS): left subtree, right subtree, root
• Level order (BFS): all nodes at depth 0, then depth 1, then depth 2, and so on

The first three are depth-first, typically implemented with recursion or an explicit stack. Level order is breadth-first, and the natural tool is a queue.

In the tree above, level order traversal visits node 1 first (level 0), then nodes 2 and 3 (level 1), and finally nodes 4 and 5 (level 2). The output is [1, 2, 3, 4, 5].

Understanding the Problem

Given: The root of a binary tree. Task: Return a list of node values visited in level order (left to right, top to bottom). Return: A List<Integer> with values in BFS order.

Here is the example from the problem definition:

tree: 1 2 3 # # 4 5

    1
   / \
  2   3
     / \
    4   5

levelOrder(root) -> [1, 2, 3, 4, 5]

Edge Cases

1. Null root: Return an empty list.
2. Single node: Return a list with just that value.
3. Skewed tree (every node has only one child): The queue never holds more than one node, but the traversal still works identically.
4. Complete tree: The last level can hold up to half the total nodes, which drives the worst-case queue size.

Solution Approach

The key observation is that a queue naturally maintains level ordering. When you enqueue the root and then repeatedly dequeue a node while enqueuing its children, every child at depth d enters the queue after all nodes at depth d-1 have been enqueued. Because the queue is FIFO, those depth d-1 nodes will all be processed first.

Here is the step-by-step reasoning:

1. Create an empty result list and an empty queue.
2. If the root is null, return the empty list immediately.
3. Enqueue the root.
4. While the queue is not empty, dequeue the front node, append its value to the result, and enqueue its left and right children if they exist.
5. When the queue empties, every node has been visited in level order.

Why a Queue Works

Think of the queue as a waiting line at a theme park. Everyone in line arrived before the people behind them. When you add the root's children (level 1) to the back of the line, they cannot be served until the root (level 0) has been fully processed. When level 1 nodes are processed, their children (level 2) go to the back, behind any remaining level 1 nodes. This cascading effect is what produces the level-by-level ordering.

The colors above show the traversal order: green for level 0, blue for level 1, purple for level 2.

Tracing Through the Algorithm

Let's trace the queue state as we process the example tree:

Each step dequeues the front node, records its value, and enqueues its children. By the time the queue is empty, the result list contains every node in level order.

Implementation

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

public class Solution {
  public List<Integer> levelOrder(TreeNode root) {
    // Output list for node values
    List<Integer> result = new ArrayList<>();

    if (root == null) return result;

    // FIFO queue drives the BFS
    Deque<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
      TreeNode node = queue.poll();
      result.add(node.data);

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

    return result;
  }
}

A few things to notice about this implementation:

• We use Deque<TreeNode> backed by LinkedList rather than the older Queue interface. Deque gives us offer() and poll() with clear FIFO semantics.
• The null check for the root avoids a NullPointerException on the first queue.offer(root) call.
• Each node is enqueued exactly once and dequeued exactly once, so the loop body runs n times total.

Interactive Traversal

Watch the algorithm in action on our example tree. Each step shows which node is being dequeued and processed:

Complexity Analysis

Time Complexity: O(n)

Every node enters the queue once and leaves once. Inside the loop, we do constant work per node: one poll(), one add(), and up to two offer() calls. That gives us O(n) total, where n is the number of nodes.

Space Complexity: O(n)

The queue holds at most one complete level of the tree at any time. For a balanced binary tree with n nodes, the widest level (the leaves) has roughly n/2 nodes, so the queue can grow to O(n).

In the balanced tree above, level 2 contains 4 nodes. When we finish processing level 1, all 4 nodes from level 2 are in the queue simultaneously.

For a skewed tree, the queue never holds more than one node because each level has exactly one node:

So the space complexity ranges from O(1) for a skewed tree to O(n) for a complete tree. We report the worst case: O(n).

Common Pitfalls

1. Using a stack instead of a queue. A stack reverses the processing order. You would visit right children before left children at alternating levels, producing zigzag output instead of level order.

2. Forgetting the null check on root. If root is null and you try to enqueue it, you will either get a NullPointerException or enqueue null and later crash when accessing node.data.

3. Checking node.left or node.right after using node.data. This is actually fine in Java, but in languages with ownership semantics (Rust) or strict null checks (Kotlin), the ordering and null guards matter more.

4. Confusing level order with preorder. Both visit the root first, and for many trees the first few values match. But preorder dives left before visiting siblings, while level order visits all siblings before going deeper.

Interview Tips

When you get this problem in an interview:

1. Clarify the output format. Some interviewers want a flat list, others want a list of lists grouped by level. The grouped version requires tracking the queue size at the start of each level.

2. State the data structure up front. Say "I will use a queue for BFS" before writing any code. This tells the interviewer you know the right tool.

3. Draw the queue state. Sketch the queue contents after each dequeue, just like the state evolution diagram above. This demonstrates your understanding of the FIFO property.

4. Mention the follow-up. After solving the basic version, mention related problems: zigzag level order, right-side view, or maximum width. This shows breadth of knowledge.

5. Discuss DFS as an alternative. You can do level order traversal recursively by passing the depth and using a list of lists. Mention this to show you understand both approaches, then explain why the iterative BFS version is more natural.

Key Takeaways

• Level order traversal is BFS on a tree. The queue's FIFO property guarantees nodes are processed level by level, left to right.
• The algorithm runs in O(n) time because each node is enqueued and dequeued exactly once, with O(1) work per node.
• Space complexity is O(n) in the worst case, determined by the widest level of the tree (up to n/2 nodes for a complete binary tree).
• This pattern is the foundation for dozens of BFS-based problems: shortest path in unweighted graphs, multi-source BFS, level-grouped traversals, and tree width calculations.
• Always check for a null root before enqueuing. This single guard prevents the most common runtime error in tree BFS implementations.

Solutions in Other Languages

Python

from collections import deque

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

        queue = deque()
        queue.append(root)

        while queue:
            node = queue.popleft()
            result.append(node.data)

            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)

        return result

JavaScript

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

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

    while (queue.nonEmpty()) {
      const node = queue.dequeue();
      result.push(node.data);

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

    return result;
  }
}

TypeScript

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

    const queue = new Queue<TreeNode>();
    queue.offer(root);

    while (!queue.isEmpty()) {
      const node = queue.poll()!;
      result.push(node.data);

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

    return result;
  }
}

C++

#include <queue>
#include <vector>

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

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

    while (!queue.empty()) {
      TreeNode *node = queue.front();
      queue.pop();
      result.push_back(node->data);

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

    return result;
  }
};

Go

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

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

    for !queue.IsEmpty() {
        node := queue.Poll().(*TreeNode)
        result = append(result, node.Data)

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

    return result
}

Scala

import scala.collection.mutable

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

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

    while (queue.nonEmpty) {
      val node = queue.dequeue
      result.append(node.data)

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

    result.toList
  }
}

Kotlin

import java.util.ArrayDeque

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

    val queue = ArrayDeque<TreeNode>()
    queue.addLast(root)

    while (queue.isNotEmpty()) {
      val node = queue.removeFirst()
      result.add(node.data)

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

    return result
  }
}

Rust

use std::collections::VecDeque;

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

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

        while let Some(node) = queue.pop_front() {
            result.push(node.data);

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

        result
    }
}

Swift

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

        var queue: [TreeNode] = [root]

        while !queue.isEmpty {
            let node = queue.removeFirst()
            result.append(node.data)

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

        return result
    }
}

Dart

import 'dart:collection';

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

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

    while (queue.isNotEmpty) {
      TreeNode node = queue.removeFirst();
      result.add(node.data);

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

    return result;
  }
}

C#

using System.Collections.Generic;

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

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

        while (queue.Count > 0) {
            var node = queue.Dequeue();
            result.Add(node.data);

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

        return result;
    }
}

Ruby

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

    queue = [root]

    while !queue.empty?
      node = queue.shift
      result.push(node.data)

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

    result
  end
end

PHP

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

        $queue = [$root];

        while (!empty($queue)) {
            $node = array_shift($queue);
            $result[] = $node->data;

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

        return $result;
    }
}

Practice Makes Perfect

Once you are comfortable with level order traversal, try these related problems to solidify your BFS skills:

• Bottom-up level order traversal (reverse the level grouping)
• Zigzag level order traversal (alternate left-to-right and right-to-left)
• Binary tree right side view (last node at each level)
• Maximum width of a binary tree

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 companies. Whether you are brushing up on BFS fundamentals or tackling advanced graph problems, consistent practice is what separates candidates who pass from those who don't.