17  Binary-Tree Level-Order Traversal

Rank 15 · Pattern: breadth-first search with queue snapshots · Target: \(O(n)\) time

17.1 Problem definition

Given the root of a binary tree, return its node values grouped into one list per depth, proceeding from the root level downward.

17.2 Clarifying questions

  1. Should each level contain node values or node references?
  2. In what order should nodes within a level appear?
  3. What should an empty tree return?
  4. Can I assume the input is a valid tree with no cycles or shared child nodes?

17.3 Sample answers

  1. Return the integer values.
  2. List them from left to right within each level.
  3. Return an empty outer list.
  4. Yes. The input is a conventional binary tree.

17.4 Special data structures: TreeNode and queue

The conventional binary-tree node has one value and up to two child links.

static class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
}

Use Queue<TreeNode> with ArrayDeque: offer adds at the back, poll removes from the front, and size reports queued nodes.

TreeNode stores left and right references. collections.deque supplies append, popleft, and len.

Children use Option<Box<TreeNode>>. A VecDeque<&TreeNode> queues borrowed node references, so traversal neither moves nor clones the tree.

       3          root
      / \
     9  20        depth 1
        / \
       15  7      depth 2

17.5 Approach and invariant

Enqueue the root. At the start of each outer iteration, snapshot levelSize = queue.size(). Remove exactly that many nodes into one level while enqueuing their children for the next level.

start:       queue [3]          levelSize 1
after 3:     queue [9,20]       emit [3]
after level: queue [15,7]       emit [9,20]
last:        queue []           emit [15,7]

Invariant: at the start of an outer iteration, the queue contains exactly the nodes at the next depth, from left to right. During its fixed-size inner loop, appended children belong only to the following depth.

17.6 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class LevelOrderTraversalSolution {
    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
        TreeNode(int value) { this.value = value; }
    }

    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> answer = new ArrayList<>();
        if (root == null) {
            return answer;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.value);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            answer.add(level);
        }
        return answer;
    }

    @Test public void emptyTreeHasNoLevels() {
        assertTrue(levelOrder(null).isEmpty());
    }

    @Test public void singleNodeCreatesOneLevel() {
        assertEquals(List.of(List.of(4)), levelOrder(new TreeNode(4)));
    }

    @Test public void visitsChildrenLeftToRight() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        assertEquals(List.of(List.of(1), List.of(2, 3)), levelOrder(root));
    }

    @Test public void visitsBalancedTreeByLevel() {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        assertEquals(List.of(List.of(3), List.of(9, 20), List.of(15, 7)),
                     levelOrder(root));
    }

    @Test public void handlesSkewedTree() {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);
        assertEquals(List.of(List.of(1), List.of(2), List.of(3)), levelOrder(root));
    }

    @Test public void preservesOrderAcrossMissingChildren() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(5);
        assertEquals(
            List.of(List.of(1), List.of(2, 3), List.of(4, 5)),
            levelOrder(root)
        );
    }

    public static void main(String[] args) {
        JUnitCore.main("LevelOrderTraversalSolution");
    }
}
import unittest
from collections import deque


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


def level_order(root):
    if root is None:
        return []

    answer = []
    queue = deque([root])

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        answer.append(level)

    return answer


class LevelOrderTraversalTests(unittest.TestCase):
    def test_empty_tree(self):
        self.assertEqual([], level_order(None))

    def test_single_node(self):
        self.assertEqual([[4]], level_order(TreeNode(4)))

    def test_visits_children_left_to_right(self):
        root = TreeNode(1, TreeNode(2), TreeNode(3))
        self.assertEqual([[1], [2, 3]], level_order(root))

    def test_visits_balanced_tree_by_level(self):
        root = TreeNode(
            3,
            TreeNode(9),
            TreeNode(20, TreeNode(15), TreeNode(7)),
        )
        self.assertEqual([[3], [9, 20], [15, 7]], level_order(root))

    def test_handles_skewed_tree(self):
        root = TreeNode(1, right=TreeNode(2, right=TreeNode(3)))
        self.assertEqual([[1], [2], [3]], level_order(root))

    def test_preserves_order_across_missing_children(self):
        root = TreeNode(
            1,
            TreeNode(2, right=TreeNode(4)),
            TreeNode(3, left=TreeNode(5)),
        )
        self.assertEqual([[1], [2, 3], [4, 5]], level_order(root))


if __name__ == "__main__":
    unittest.main()
use std::collections::VecDeque;

#[derive(Debug)]
pub struct TreeNode {
    pub value: i32,
    pub left: Link,
    pub right: Link,
}

pub type Link = Option<Box<TreeNode>>;

impl TreeNode {
    pub fn new(value: i32) -> Self {
        Self {
            value,
            left: None,
            right: None,
        }
    }
}

pub fn level_order(root: &Link) -> Vec<Vec<i32>> {
    let Some(root) = root.as_deref() else {
        return Vec::new();
    };

    let mut answer = Vec::new();
    let mut queue = VecDeque::from([root]);

    while !queue.is_empty() {
        let mut level = Vec::new();
        for _ in 0..queue.len() {
            let node = queue.pop_front().unwrap();
            level.push(node.value);
            if let Some(left) = node.left.as_deref() {
                queue.push_back(left);
            }
            if let Some(right) = node.right.as_deref() {
                queue.push_back(right);
            }
        }
        answer.push(level);
    }

    answer
}

#[cfg(test)]
mod tests {
    use super::*;

    fn node(value: i32) -> Box<TreeNode> {
        Box::new(TreeNode::new(value))
    }

    #[test]
    fn empty_tree() {
        assert_eq!(Vec::<Vec<i32>>::new(), level_order(&None));
    }

    #[test]
    fn single_node() {
        assert_eq!(vec![vec![4]], level_order(&Some(node(4))));
    }

    #[test]
    fn visits_children_left_to_right() {
        let mut root = node(1);
        root.left = Some(node(2));
        root.right = Some(node(3));
        assert_eq!(vec![vec![1], vec![2, 3]], level_order(&Some(root)));
    }

    #[test]
    fn visits_balanced_tree_by_level() {
        let mut root = node(3);
        root.left = Some(node(9));
        let mut right = node(20);
        right.left = Some(node(15));
        right.right = Some(node(7));
        root.right = Some(right);

        assert_eq!(
            vec![vec![3], vec![9, 20], vec![15, 7]],
            level_order(&Some(root))
        );
    }

    #[test]
    fn handles_skewed_tree() {
        let mut root = node(1);
        let mut second = node(2);
        second.right = Some(node(3));
        root.right = Some(second);
        assert_eq!(vec![vec![1], vec![2], vec![3]], level_order(&Some(root)));
    }
}

Without the levelSize snapshot, children would be consumed in the same level in which they were enqueued.

17.7 High-value tests

Tree Expected
empty []
one node 4 [[4]]
balanced sample [[3],[9,20],[15,7]]
left-skewed 1-2-3 [[1],[2],[3]]
missing left child preserves right child position in visit order

17.8 Complexity and correctness

Each node is enqueued and dequeued once, so time is \(O(n)\). The queue holds at most the maximum tree width \(w\), giving \(O(w)\) traversal space; the returned result stores \(O(n)\) values.

The queue invariant proves that each emitted list contains exactly one depth in left-to-right order. Children are enqueued left before right, preserving ordering at the next depth. Every reachable node has one parent enqueue (except the root), so every node appears exactly once.

17.9 If the interviewer pushes

  • A depth-first traversal can group by depth by extending an output list, but uses recursion depth \(O(h)\).
  • Zigzag order can reverse alternating levels or use a deque.
  • Return averages or maxima by aggregating each fixed-size level instead of storing all values.
  • For enormous breadth, any exact level-order traversal still needs memory proportional to a frontier.

17.10 TDD interview script

Confirm that the result contains values grouped by depth, nodes are left-to-right within a level, null returns an empty outer list, and the input is a valid tree. Then write this test list:

  1. Empty tree
  2. Singleton
  3. Two children
  4. Balanced example
  5. Skewed tree
  6. Missing children across two parents

Use one focused red–green–refactor cycle per tree shape. Build fixtures explicitly so their topology is visible, observe the intended failure, make the smallest queue change, and rerun the complete example. Assert the nested result lists, not queue implementation details.

From book/src, run:

./java/run.sh LevelOrderTraversalSolution
./python/run.sh level_order_traversal_solution
./rust/run.sh level_order_traversal_solution

When adding the first multi-level tree, state why levelSize is captured before the inner loop: children enqueued during this level belong to the next level and must not be consumed immediately.

17.10.1 Pseudocode

answer = empty list
if root is null:
    return answer

queue = queue containing root
while queue is not empty:
    levelSize = queue.size
    level = empty list
    repeat levelSize times:
        node = dequeue
        append node.value to level
        enqueue node.left if present
        enqueue node.right if present
    append level to answer

return answer

At the start of each outer iteration, the queue contains exactly the next depth’s nodes in left-to-right order. The fixed-size inner loop preserves that boundary.

17.10.2 TDD sequence

Step Test code added Production code added or changed
1. Empty tree emptyTreeHasNoLevels Return an empty result before attempting to enqueue a null root.
2. Root level singleNodeCreatesOneLevel Enqueue the root, dequeue it into one level, and append that level.
3. Left-to-right children visitsChildrenLeftToRight Enqueue left before right and process the next queue frontier in FIFO order.
4. Level boundary visitsBalancedTreeByLevel Snapshot queue.size() and remove exactly that many nodes before appending the level.
5. Narrow frontier handlesSkewedTree Continue outer iterations with a one-node queue and ignore absent children.
6. Sparse ordering preservesOrderAcrossMissingChildren Enqueue only present children while retaining parent order across the next level.

The progression grows breadth-first traversal from one node and uses a sparse-tree regression to distinguish true queue order from assumptions about complete trees.