Binary Tree Level Order Traversal

Medium Problem 70 of 151 Java and Python

Problem

Given the root of a binary tree, return the level order traversal of its values: left to right, one list per level, from the top.

Example 1

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

Example 2

Input: root = []
Output: []

Constraints

0 ≤ number of nodes ≤ 2000

Explanation

A queue visits nodes in the order they were discovered, which for a tree means level by level. To split the output into levels, take exactly queue.size() nodes at the start of each round.

Approach 1 · Better

DFS with a depth index

Time O(n)
Space O(h) recursion

Do a preorder DFS that carries the depth and appends each value to result[depth]. Visiting left before right keeps each level in order.

dfs(node, depth): if depth == result.size(), add a new empty level.
Append the value to result[depth], then recurse left and right with depth + 1.

Java

import java.util.*;

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<>());
        }
        result.get(depth).add(node.val);
        dfs(node.left, depth + 1, result);
        dfs(node.right, depth + 1, result);
    }
}

Python

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []

        def dfs(node, depth):
            if not node:
                return
            if depth == len(result):
                result.append([])
            result[depth].append(node.val)
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        dfs(root, 0)
        return result

Approach 2 · Optimal

BFS with a queue

Time O(n)
Space O(w)

Each round, remove all nodes of the current level from the queue, record their values and enqueue their children.

Start the queue with the root.
While the queue is not empty: size = queue.size(); pop size nodes into a level list, pushing their children.
Append the level list to the result.

Java

import java.util.*;

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.add(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            result.add(level);
        }
        return result;
    }
}

Python

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
        queue = deque([root] if root else [])
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        return result

Complexity compared

Approach	Time	Space
Better DFS with a depth index	O(n)	O(h) recursion
Optimal BFS with a queue	O(n)	O(w)

Key takeaways

Snapshot queue.size() before the inner loop: the queue grows while you process the level.
This template also solves Right Side View, Zigzag, Average of Levels and Minimum Depth.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem