Traversal

Level-Order (BFS)

Visit all nodes at depth 0, then depth 1, then depth 2, etc. Use a queue. At each step, process all nodes at the current level and enqueue their children. Gives you the tree layer by layer.

O(n)

How It Works

Level-order traversal visits a tree breadth-first: the root, then all depth-1 nodes, then depth-2, and so on. A queue drives the process — dequeue a node, record it, enqueue its children. To split output by level, snapshot the queue size before each round and process exactly that many nodes; everything enqueued during the round belongs to the next level.

Every node is enqueued and dequeued once, giving O(n) time. The queue's peak size is the tree's maximum width, so space is O(w), which reaches O(n) for bushy trees but stays small for skewed ones.

Step-by-Step Visualization

Level-order traversal (BFS)

Level 0[3]

1/4

Code

Java

static List<List<Integer>> levelOrder(TreeNode root) {
  if (root == null) return new ArrayList<>();
  List<List<Integer>> result = new ArrayList<>();
  Queue<TreeNode> queue = new LinkedList<>();
  queue.add(root);

  while (!queue.isEmpty()) {
    List<Integer> level = new ArrayList<>();
    int size = queue.size();
    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;
}

Tips & Gotchas

1Use a queue (BFS). Process one level at a time

2At each level, note queue size = number of nodes at this level

3Process exactly that many nodes, adding their children for next level

Practice Problems

1Binary Tree Level Order Traversal
2Binary Tree Zigzag Level Order Traversal
3Binary Tree Right Side View
4Average of Levels in Binary Tree

About the Traversal Pattern

There are four ways to visit every node in a tree. Three use DFS (going deep before going wide) with different orderings, and one uses BFS (going wide before going deep). Each ordering is useful for different problems.

Key insight

Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.

Common Trees Interview Problems

Maximum Depth of Binary Tree
Validate BST
Binary Tree Level Order Traversal
Lowest Common Ancestor
Serialize and Deserialize Binary Tree
Diameter of Binary Tree

Frequently Asked Questions

When should I choose BFS over DFS for a tree problem?

Choose BFS when the answer is organized by depth — per-level aggregates, the first node meeting a condition closest to the root, or minimum depth. DFS is usually simpler when answers combine results from whole subtrees.

How do I keep track of where one level ends and the next begins?

Capture the queue's size at the start of each iteration and process exactly that many dequeues. All children added during those dequeues form the next level, so no sentinel markers are needed.