Skip to main content

Binary Tree Level Order Traversal

LeetCode 102 | Difficulty: Medium​

Medium

Problem Description​

Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).

Examples​

Example 1:

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

Tree visualization:

Result: Level 0: [3] | Level 1: [9, 20] | Level 2: [15, 7]

Approach​

BFS with Queue (Level-by-Level)​

Use a queue to process nodes level by level. The key insight: at each level, the queue contains exactly the nodes at that level.

Algorithm:

  1. Start with root in queue
  2. While queue is not empty:
    • Record size = queue length (number of nodes at this level)
    • Process exactly size nodes, adding their values to current level list
    • Enqueue children of each processed node
  3. Add current level list to result
Clean BFS — O(n)
public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        if (root == null) return result;
        
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        
        while (queue.Count > 0) {
            int levelSize = queue.Count;
            var level = new List<int>();
            
            for (int i = 0; i < levelSize; i++) {
                var node = queue.Dequeue();
                level.Add(node.val);
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            
            result.Add(level);
        }
        
        return result;
    }
}
Why capture levelSize BEFORE the loop?

The queue size changes as we enqueue children. Capturing levelSize = queue.Count before the inner loop ensures we only process nodes from the current level.

Solution: Two-Queue Approach​

This was my original accepted submission, using two queues to alternate between levels:

Two-Queue Approach
public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        Queue<TreeNode> q1 = new Queue<TreeNode>();
        Queue<TreeNode> q2 = new Queue<TreeNode>();
        List<IList<int>> levelOrder = new List<IList<int>>();
        if (root == null) return levelOrder;
        
        q1.Enqueue(root);
        bool isFirst = true;
        
        while (q1.Count != 0 || q2.Count != 0) {
            var current = isFirst ? q1 : q2;
            var next = isFirst ? q2 : q1;
            List<int> temp = new List<int>();
            
            while (current.Count != 0) {
                var popped = current.Dequeue();
                temp.Add(popped.val);
                if (popped.left != null) next.Enqueue(popped.left);
                if (popped.right != null) next.Enqueue(popped.right);
            }
            
            levelOrder.Add(temp);
            isFirst = !isFirst;
        }
        
        return levelOrder;
    }
}

Solution: DFS (Recursive)​

Track the level number during DFS, and add each node's value to the corresponding level list:

DFS Recursive Approach
public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        DFS(root, 0, result);
        return result;
    }

    private void DFS(TreeNode node, int level, List<IList<int>> result) {
        if (node == null) return;
        
        // Create new level list if needed
        if (result.Count == level) {
            result.Add(new List<int>());
        }
        
        result[level].Add(node.val);
        DFS(node.left, level + 1, result);
        DFS(node.right, level + 1, result);
    }
}

Complexity Analysis​

ApproachTimeSpaceNotes
BFS (single queue)$O(n)$$O(w)$$w$ = max width of tree
BFS (two queues)$O(n)$$O(w)$Same, slightly more memory
DFS (recursive)$O(n)$$O(h)$$h$ = height of tree (call stack)

For a balanced binary tree: $w = n/2$, $h = \log n$ For a skewed tree: $w = 1$, $h = n$

Interview Tips​

BFS is the Standard Approach
  • In interviews, BFS with a single queue is the cleanest and most expected solution
  • The "capture level size" trick is the key pattern for all level-order problems
  • DFS works but is less intuitive for level-order questions

Follow-up Questions​