53.Binary Tree Level Order Traversal

MediumBlind 75Trees · 8/15

Problem

Given the root of a binary tree, return the level order traversal of its node values: a list of levels, from top to bottom, where each level lists its values from left to right.

Examples

Input:  root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Input:  root = [1]
Output: [[1]]

Input:  root = []
Output: []

Constraints

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

💡 Key Insight

A FIFO queue naturally visits nodes in level order: everything on level d is enqueued before anything on level d + 1. By snapshotting the queue size at the start of each round, we know exactly how many nodes belong to the current level and can group them into one list.

Brute Force (Collect One Level at a Time)

TimeO(n · h)SpaceO(h)

Intuition

Compute the tree height H. Then, for each level d from 0 to H - 1, run a fresh DFS from the root that only records nodes at depth d. Pre-order visits left before right, so values on each level come out in left-to-right order.

Algorithm

H = height(root).
For d in 0 .. H - 1:
- Create an empty list, run collect(root, d, list), append the list.
collect(node, d, list): if node is null return; if d == 0 add node.val; else recurse on both children with d - 1.

Visualization

H = 3
d = 0: DFS stops at depth 0          -> [3]
d = 1: DFS goes 1 deep               -> [9, 20]
d = 2: DFS goes 2 deep               -> [15, 7]
Nodes near the top are re-visited on every pass.

Code

java

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        int height = height(root);
        for (int d = 0; d < height; d++) {
            List<Integer> level = new ArrayList<>();
            collect(root, d, level);
            result.add(level);
        }
        return result;
    }

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

    // add every node exactly `depth` levels below `node`, left to right
    private void collect(TreeNode node, int depth, List<Integer> level) {
        if (node == null) return;
        if (depth == 0) {
            level.add(node.val);
            return;
        }
        collect(node.left, depth - 1, level);
        collect(node.right, depth - 1, level);
    }
}

Complexity

Time: O(n · h) — each of the h passes may touch every node above its target depth; O(n²) for a skewed tree.
Space: O(h) — recursion depth (excluding the output).

DFS with Depth Index

TimeO(n)SpaceO(h)

Intuition

Do a single pre-order DFS carrying the current depth. Use depth as an index into the result: the first time we reach a new depth, append a new empty list. Because left is visited before right, each level's list is filled in left-to-right order.

Algorithm

dfs(node, depth): if node is null, return.
If depth == result.size(), add a new empty list.
result.get(depth).add(node.val).
Recurse on node.left and node.right with depth + 1.

Visualization

visit 3  (depth 0) -> result = [[3]]
visit 9  (depth 1) -> result = [[3],[9]]
visit 20 (depth 1) -> result = [[3],[9,20]]
visit 15 (depth 2) -> result = [[3],[9,20],[15]]
visit 7  (depth 2) -> result = [[3],[9,20],[15,7]]

Code

java

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int depth, List<List<Integer>> result) {
        if (node == null) {
            return;
        }
        if (depth == result.size()) {
            result.add(new ArrayList<>()); // first node seen on this level
        }
        result.get(depth).add(node.val);
        dfs(node.left, depth + 1, result);
        dfs(node.right, depth + 1, result);
    }
}

Complexity

Time: O(n) — every node is visited once.
Space: O(h) — recursion depth (excluding the output).

BFS with a QueueOptimal

TimeO(n)SpaceO(w)

Intuition

This is the textbook way. A queue processes nodes in exactly the order the output wants. At the start of each round, the queue contains precisely the nodes of one level; record size = queue.size(), poll that many nodes into a list, and enqueue their children for the next round.

Algorithm

If root is null, return [].
Enqueue root.
While the queue is not empty:
- size = queue.size(); create level.
- Repeat size times: poll a node, add its value to level, enqueue its non-null children.
- Append level to the result.
Return the result.

Dry Run

flowchart TD
    Q0["queue: [3]<br/>size = 1"] -->|"poll 3, push 9, 20"| L0["level [3]"]
    L0 --> Q1["queue: [9, 20]<br/>size = 2"]
    Q1 -->|"poll 9, poll 20, push 15, 7"| L1["level [9, 20]"]
    L1 --> Q2["queue: [15, 7]<br/>size = 2"]
    Q2 -->|"poll 15, poll 7"| L2["level [15, 7]"]
    L2 --> D["queue empty<br/>[[3],[9,20],[15,7]]"]

Code

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Deque<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);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
}

Complexity

Time: O(n) — each node is enqueued and polled once.
Space: O(w) — the queue holds at most one level, about n/2 nodes for a complete tree.

Complexity Comparison

Approach	Time	Space
Brute Force (Collect One Level at a Time)	O(n · h)	O(h)
DFS with Depth Index	O(n)	O(h)
BFS with a Queue	O(n)	O(w)

Common Pitfalls

Using queue.size() directly as the for loop bound — it grows while children are enqueued, so levels bleed into each other. Snapshot it first.
Returning [[]] for an empty tree instead of [].
Enqueuing null children into an ArrayDeque, which throws NullPointerException; check before offering.
In the DFS version, visiting right before left reverses each level's order.