Binary Tree Level Order Traversal

Master this topic with zero to advance depth.

Binary Tree Level Order Traversal

BFS traversal.

Medium

Approach 1

Level I: Recursive depth-first (DFS)

Intuition

We can use recursion to traverse the tree. By passing the current depth (level) as an argument, we can add each node's value to a list corresponding to its level. If the list for a level doesn't exist yet, we create it.

Thought Process

Maintain a list of lists res.
Call helper(node, level).
If res.size() == level, add a new inner list.
res.get(level).add(node.val).
Recurse left and right with level + 1.

⏱ O(N)💾 O(H) (due to recursion stack where H is tree height)

Detailed Dry Run

Node	Level	Result (State)
3	0	[[3]]
9	1	[[3], [9]]
20	1	[[3], [9, 20]]
15	2	[[3], [9, 20], [15]]

java

import java.util.*;

public class Main {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        helper(root, 0, res);
        return res;
    }

    private void helper(TreeNode node, int level, List<List<Integer>> res) {
        if (node == null) return;
        if (res.size() == level) res.add(new ArrayList<>());
        res.get(level).add(node.val);
        helper(node.left, level + 1, res);
        helper(node.right, level + 1, res);
    }

    public static void main(String[] args) {
        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);
        System.out.println(new Main().levelOrder(root)); // [[3], [9, 20], [15, 7]]
    }
}

Approach 2

Level II: Iterative DFS (using Stack)

Intuition

While BFS is the natural choice for level-order, we can simulate it using DFS with depth tracking. We maintain a stack of (node, depth). If the result list size is equal to the current depth, we add a new empty list. Then, we add the node value to the list corresponding to its depth.

Logic

Use a Stack for DFS.
Track depth for each node.
res[depth].add(node.val).
Note: Push right child first, then left to maintain left-to-right order in levels.

⏱ O(N)💾 O(N)

Detailed Dry Run

Stack	Depth	res state
[(3,0)]	0	[[3]]
[(20,1), (9,1)]	1	[[3], [9]]
[(20,1)]	1	[[3], [9, 20]]

java

import java.util.*;

public class Main {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Stack<Object[]> stack = new Stack<>();
        stack.push(new Object[]{root, 0});
        while (!stack.isEmpty()) {
            Object[] curr = stack.pop();
            TreeNode node = (TreeNode)curr[0];
            int depth = (int)curr[1];
            if (res.size() == depth) res.add(new ArrayList<>());
            res.get(depth).add(node.val);
            if (node.right != null) stack.push(new Object[]{node.right, depth + 1});
            if (node.left != null) stack.push(new Object[]{node.left, depth + 1});
        }
        return res;
    }
}

Approach 3

Level III: Optimal (BFS with Queue)

Intuition

Thought Process

The standard way to perform level-order traversal is Breadth-First Search (BFS) using a Queue. We process the tree level by level. For each level, we record how many nodes are currently in the queue; this count is the number of nodes in that specific level.

Diagram

Queue: [3]  -> Level nodes: [3]
Queue: [9, 20] -> Level nodes: [9, 20]
Queue: [15, 7] -> Level nodes: [15, 7]

⏱ O(N) (each node visited once)💾 O(N) (queue stores maximum level width)

Detailed Dry Run

Queue	Level Size	Processing	Result Area
[3]	1	Pop 3, Push 9, 20	[3]
[9, 20]	2	Pop 9, Pop 20, Push 15, 7	[9, 20]
[15, 7]	2	Pop 15, Pop 7	[15, 7]

java

public class Main {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; 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;
    }
}

⚠️ Common Pitfalls & Tips

Empty tree checking is vital (if root == null). Forget this and the while loop might run on a null list or throw errors.

← Previous QuestionValidate Binary Search Tree

Next Question →Lowest Common Ancestor of a Binary Tree

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.