Level by Level with a Queue

Top floor first

Sometimes you want the tree level by level: the root, then all its children, then all grandchildren. Recursion goes deep, not wide – so we use a queue (Module 11) instead:

• Put the root in the queue.
• Take a node from the front, handle it, and add its children to the back.
• Repeat until the queue is empty.

To know where one level ends, look at the queue's size at the start of each level – that's exactly how many nodes that level has:

import java.util.ArrayDeque;

class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int value) { this.value = value; }
}

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(3);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(6);
        root.right.right = new TreeNode(14);

        ArrayDeque<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();               // nodes on this level
            StringBuilder line = new StringBuilder("level " + level + ":");
            for (int i = 0; i < size; i++) {
                TreeNode n = queue.poll();
                line.append(' ').append(n.value);
                if (n.left != null) queue.offer(n.left);
                if (n.right != null) queue.offer(n.right);
            }
            System.out.println(line);
            level++;
        }
    }
}

Output

level 0: 8
level 1: 3 10
level 2: 1 6 14

Think of it like this: Announcing exam results by row in a hall: finish row 1, then row 2, then row 3 – everyone in a row before anyone in the next.

Common mistake: ArrayDeque does not allow null. Only offer a child after checking it isn't null.

In the challenges, a tree is given as a numbered list of nodes, each with its value and the numbers of its left and right children (-1 = none). The solutions show a small build method that turns that into TreeNode objects – feel free to copy it.