☕ DSA Java Articles

Topics › Binary Trees › Traversals

Level Order Traversal

Easy TUF ID 134 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return its values level by level: first the root, then all nodes at depth 1 from left to right, then all nodes at depth 2 from left to right, and so on. The answer is a list of lists, one inner list per level. An empty tree gives an empty outer list.

Constraints: between 0 and 10^5 nodes (LeetCode uses at most 2000), arbitrary 32-bit values. The tree can be very unbalanced, even a single chain.

Trees are written in LeetCode’s level-order form, where null marks a missing child.

Example 1

      3
     / \
    9   20
       /  \
      15   7
root = [3, 9, 20, null, null, 15, 7]
answer = [[3], [9, 20], [15, 7]]

Example 2

      1
     / \
    2   3
     \   \
      4   5
root = [1, 2, 3, null, 4, null, 5]
answer = [[1], [2, 3], [4, 5]]   // gaps inside a level are skipped; 4 and 5 are still neighbours

Preorder, inorder and postorder are depth-first: they finish one branch before starting the next. Level order is breadth-first: it finishes one depth before starting the next. That makes it the natural tool for anything phrased in terms of levels: the view from one side, the width at each level, the minimum depth, zigzag order, and connecting nodes to their right neighbour.

Approach 1: Brute force, one pass per level

Intuition. The most literal reading is: for depth 0, list all nodes at depth 0; for depth 1, list all nodes at depth 1; and so on, down to the last level. A recursive helper can collect the nodes at a given depth d by walking down and decrementing d; when it reaches 0, the current node is at the wanted depth. Visiting left before right keeps each level in left-to-right order. We first compute the height so we know how many levels there are.

Algorithm.

  1. Compute h, the number of levels.
  2. For each d from 0 to h - 1: walk the tree from the root, appending every node reached with d == 0, and add that list to the answer.
static List<List<Integer>> bruteForce(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    int h = height(root);
    for (int d = 0; d < h; d++) {
        List<Integer> level = new ArrayList<>();
        collect(root, d, level);
        levels.add(level);
    }
    return levels;
}

private static void collect(TreeNode node, int d, List<Integer> level) {
    if (node == null) return;
    if (d == 0) {                             // this node is exactly at the wanted depth
        level.add(node.val);
        return;
    }
    collect(node.left, d - 1, level);         // left first keeps the level in left-to-right order
    collect(node.right, d - 1, level);
}

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

Complexity. Time O(n * h) in the worst case: the pass for depth d touches every node at depth d or less. On a perfect tree each level is twice the size of the one above, so the passes add up to only about 2n visits, but on a chain (h = n) they cost 1 + 2 + ... + n, which is O(n^2). Space O(h) for the recursion. Every level is recomputed from scratch, which is the waste the next approaches remove.

Approach 2: One DFS that carries the depth

Intuition. We do not need one pass per level. A single depth-first walk can carry the current depth along and append each node to the list belonging to its depth. When the walk reaches a depth for the first time, that list does not exist yet, and because depths are discovered in increasing order, the new list always goes at the end.

Why are the levels still in left-to-right order even though the walk jumps between depths? Take two nodes on the same level, a to the left of b. Their lowest common ancestor has a in its left subtree and b in its right subtree, and a preorder walk finishes the entire left subtree before entering the right one. So a is appended before b.

Algorithm.

  1. Start with an empty list of levels and call dfs(root, 0).
  2. In dfs(node, depth): if node is null, return. If depth == levels.size(), append a new empty list. Append node.val to levels[depth]. Recurse left, then right, with depth + 1.
static List<List<Integer>> dfsWithDepth(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    dfs(root, 0, levels);
    return levels;
}

private static void dfs(TreeNode node, int depth, List<List<Integer>> levels) {
    if (node == null) return;
    if (depth == levels.size()) levels.add(new ArrayList<>());    // first node ever seen at this depth
    levels.get(depth).add(node.val);
    dfs(node.left, depth + 1, levels);                            // left before right keeps each level ordered
    dfs(node.right, depth + 1, levels);
}

Complexity. Time O(n): one visit per node, and every list operation is amortised O(1). Space O(h) for the recursion. That is linear, but it still relies on the call stack, so a chain of 10^5 nodes can overflow it.

Approach 3: Optimal, breadth-first search with a queue

Intuition. A queue is first-in-first-out, which is exactly the order of levels: if we put the root in, then repeatedly take a node out and put its children in, nodes come out level by level, left to right. The only extra question is where one level ends and the next begins. The answer comes from an invariant: at the start of each round, the queue contains exactly one complete level. So we read queue.size() once, take out precisely that many nodes as the current level, and everything they add to the back of the queue forms the next level.

Algorithm.

  1. If the root is null, return an empty list. Otherwise enqueue the root.
  2. While the queue is not empty:
    • Let size be the current queue size.
    • Dequeue size nodes, appending each value to a new list and enqueueing each node’s existing children.
    • Add the list to the answer.
static List<List<Integer>> bfs(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    if (root == null) return levels;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();                  // exactly the nodes of the current level
        List<Integer> level = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);      // children join the back of the queue,
            if (node.right != null) queue.offer(node.right);    // behind the rest of this level
        }
        levels.add(level);
    }
    return levels;
}

Dry run on Example 1.

Round Queue at start size Level produced Queue at end
1 [3] 1 [3] [9, 20]
2 [9, 20] 2 [9, 20] [15, 7]
3 [15, 7] 2 [15, 7] []

Why it works. The invariant holds at the start (the queue holds the root, which is level 0). If the queue holds exactly level d in left-to-right order, then dequeuing those nodes and enqueuing their children in left-then-right order puts exactly level d + 1 into the queue, again left to right, because the children of a left node come before the children of a node further right.

Complexity. Time O(n): each node is enqueued and dequeued once. Space O(w), where w is the maximum width of the tree: the queue holds at most one level plus part of the next. For a perfect tree the last level has about n / 2 nodes, so the worst case is O(n); for a chain it is O(1). There is no recursion, so the depth of the tree does not matter. The Java tests run BFS on a chain of 10^5 nodes.

Edge cases and pitfalls