Binary Tree Level Order Traversal

Medium Trees & BST Traversals Original on LeetCode

Binary Tree Level Order Traversal is a medium trees & bst problem solved with the traversals pattern. The best approach, bfs level by level, runs in O(n) time and O(w) space. Below are 2 approaches in Java, from dfs with a depth index up.

Problem

Return the values of a binary tree level by level, from top to bottom and left to right within each level.

Examples

Example 1

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

Example 2

Input: root = []
Output: []

Constraints

The tree has 0 to 2000 nodes.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
DFS with a depth index	`O(n)`	`O(h)`
BFS level by level	`O(n)`	`O(w)`

1DFS with a depth index

TimeO(n)

SpaceO(h)

Preorder DFS carrying the depth; append each value to the list for its depth.

If depth == out.size(), add a new list.
out.get(depth).add(val); recurse with depth + 1.

Java

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        dfs(root, 0, out);
        return out;
    }

    private void dfs(TreeNode n, int d, List<List<Integer>> out) {
        if (n == null) return;
        if (d == out.size()) out.add(new ArrayList<>());
        out.get(d).add(n.val);
        dfs(n.left, d + 1, out);
        dfs(n.right, d + 1, out);
    }
}

2BFS level by level

TimeO(n)

SpaceO(w)The queue holds at most one level (width w).

Use a queue. For each level, read size = q.size(), poll exactly that many nodes into one list and enqueue their children.

q = [root].
While q is not empty: size = q.size(); poll size nodes, record values, enqueue children.

Java

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        if (root == null) return out;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int i = q.size(); i > 0; i--) {
                TreeNode n = q.poll();
                level.add(n.val);
                if (n.left != null) q.add(n.left);
                if (n.right != null) q.add(n.right);
            }
            out.add(level);
        }
        return out;
    }
}

Edge cases to test

Empty tree
Unbalanced levels

Hints

Hint 1

At the start of each level, the queue holds exactly that level's nodes. Record its size before processing.

FAQ

What is the best time complexity for Binary Tree Level Order Traversal?

BFS level by level runs in O(n) time and O(w) extra space.

Which pattern does Binary Tree Level Order Traversal use?

It is a trees & bst problem that uses the traversals pattern. Other problems with the same pattern: Binary Tree Zigzag Level Order Traversal, Binary Tree Level Order Traversal II.

Is there a brute force solution for Binary Tree Level Order Traversal?

Yes. DFS with a depth index takes O(n) time and O(h) space. Preorder DFS carrying the depth; append each value to the list for its depth.

Which edge cases should I test for Binary Tree Level Order Traversal?

Empty tree; Unbalanced levels.