Tree BFS Pattern in Java - Interview Preparation Guide

BFS traverses trees level by level. It is ideal for shortest-level decisions and level-grouped output.

Core Idea

Use queue and process nodes by level size.

What we are doing actually:

Put the root in a queue.
Snapshot the current queue size before each level.
Process exactly that many nodes to keep levels separated.
Enqueue children for the next round.

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) return ans;

    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);

    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val); // Current node belongs to this level.
            if (node.left != null) q.offer(node.left); // Children belong to next level.
            if (node.right != null) q.offer(node.right);
        }
        ans.add(level); // One complete level finished.
    }
    return ans;
}

Debug steps:

print queue contents before each level starts
verify size is captured before the inner loop
test a single-node tree and an uneven tree

Problem 1: Binary Tree Level Order Traversal

Problem description: Return the nodes level by level from top to bottom.

What we are doing actually:

Use the template above directly.
Treat each queue-size snapshot as one level boundary.
Collect each level into its own list before moving on.

Problem 2: Minimum Depth of Binary Tree

Problem description: Return the number of nodes in the shortest root-to-leaf path.

What we are doing actually:

BFS explores shallower levels before deeper ones.
The first leaf we encounter must be at minimum depth.
Return immediately when that leaf appears.

public int minDepth(TreeNode root) {
    if (root == null) return 0;

    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    int depth = 1;

    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (node.left == null && node.right == null) return depth; // First leaf gives minimum depth.
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        depth++;
    }
    return depth;
}

Debug steps:

print queue nodes along with current depth
verify you return on the first leaf, not after scanning the whole tree
test a tree where the shallowest leaf is not on the leftmost branch

Problem 3: Right Side View

Problem description: Return the value visible from the right side at each tree level.

What we are doing actually:

Traverse level by level with BFS.
Process all nodes in the current level.
Record the last node processed in that level.

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) return ans;

    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);

    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
            if (i == size - 1) ans.add(node.val); // Last node in this level is rightmost in this traversal order.
        }
    }
    return ans;
}