Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Java DSA implementation can be compared directly with the rest of the DSA track.

level order Level-order traversal uses a queue to visit shallower nodes first.

Basic Implementation

                            Basic.java
                        
Replay: real traced execution (multi-file project)

                            import java.util.*;

public class Basic {
    static class Node {
        int value;
        Node left;
        Node right;
        Node(int value) { this.value = value; }
        Node(int value, Node left, Node right) { this.value = value; this.left = left; this.right = right; }
    }
    static String render(Node node) {
        if (node == null) return "_";
        if (node.left == null && node.right == null) return Integer.toString(node.value);
        return node.value + "(" + render(node.left) + "," + render(node.right) + ")";
    }
    static Node sampleTree() {
        return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
    }
    public static void main(String[] args) { Queue<Node> queue = new ArrayDeque<>(); queue.add(sampleTree()); List<Integer> output = new ArrayList<>(); while (!queue.isEmpty()) { Node node = queue.remove(); output.add(node.value); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } System.out.println(output); }
}

                        
1tree ← 4(2(1,3),6(5,7)), queue ← [4]1import java.util.*;⋯values this step4(2(1,3),6(5,7))tree[4]queue
2output ← [4], queue ← [2, 6]⋯18    }19    public static void main(String[] args) { Queue<Node> queue = new ArrayDeque<>(); queue.add(sampleTree()); List<Integer> output = new ArrayList<>(); while (!queue.isEmpty()) { Node node = queue.remove(); output.add(node.value); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } System.out.println(output); }20}values this step[4]output[2, 6]queue4dequeued
3output ← [4, 2], queue ← [6, 1, 3]⋯18    }19    public static void main(String[] args) { Queue<Node> queue = new ArrayDeque<>(); queue.add(sampleTree()); List<Integer> output = new ArrayList<>(); while (!queue.isEmpty()) { Node node = queue.remove(); output.add(node.value); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } System.out.println(output); }20}values this step[4, 2]output[6, 1, 3]queue2dequeued
4output ← [4, 2, 6], queue ← [1, 3, 5, 7]⋯18    }19    public static void main(String[] args) { Queue<Node> queue = new ArrayDeque<>(); queue.add(sampleTree()); List<Integer> output = new ArrayList<>(); while (!queue.isEmpty()) { Node node = queue.remove(); output.add(node.value); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } System.out.println(output); }20}values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued
5output ← [4, 2, 6, 1], queue ← [3, 5, 7]⋯18    }19    public static void main(String[] args) { Queue<Node> queue = new ArrayDeque<>(); queue.add(sampleTree()); List<Integer> output = new ArrayList<>(); while (!queue.isEmpty()) { Node node = queue.remove(); output.add(node.value); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } System.out.println(output); }20}values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued
6output ← [4, 2, 6, 1, 3], queue ← [5, 7]⋯18    }19    public static void main(String[] args) { Queue<Node> queue = new ArrayDeque<>(); queue.add(sampleTree()); List<Integer> output = new ArrayList<>(); while (!queue.isEmpty()) { Node node = queue.remove(); output.add(node.value); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } System.out.println(output); }20}values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued
7output ← [4, 2, 6, 1, 3, 5], queue ← [7]⋯18    }19    public static void main(String[] args) { Queue<Node> queue = new ArrayDeque<>(); queue.add(sampleTree()); List<Integer> output = new ArrayList<>(); while (!queue.isEmpty()) { Node node = queue.remove(); output.add(node.value); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } System.out.println(output); }20}values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued
8output ← [4, 2, 6, 1, 3, 5, 7], queue ← []⋯18    }19    public static void main(String[] args) { Queue<Node> queue = new ArrayDeque<>(); queue.add(sampleTree()); List<Integer> output = new ArrayList<>(); while (!queue.isEmpty()) { Node node = queue.remove(); output.add(node.value); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } System.out.println(output); }20}values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued
9public static void main(String[] args) { Queue<Node> queue = new Array…⋯18    }19    public static void main(String[] args) { Queue<Node> queue = new ArrayDeque<>(); queue.add(sampleTree()); List<Integer> output = new ArrayList<>(); while (!queue.isEmpty()) { Node node = queue.remove(); output.add(node.value); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } System.out.println(output); }20}values this step[4, 2, 6, 1, 3, 5, 7]output

Complexity

Time: O(n)
Space: O(w) queue space

Implementation notes

Java represents the tree with Node objects containing primitive int value plus Node left and Node right reference fields. Missing children are null.
The traversal declares Queue<Node> queue = new ArrayDeque<>() and enqueues the root with queue.add(sampleTree()). The queue stores node object references, not copies of subtrees.
Each loop checks !queue.isEmpty() before queue.remove(), so remove() dequeues the front node without hitting its empty-queue exception path. Non-null children are appended with queue.add(node.left) and queue.add(node.right).
output is an ArrayList<Integer> mutated with output.add(node.value), autoboxing through Integer.valueOf, so these small fixture values may be cached Integer instances. The replay shows queue and output states after every dequeue, ending with [4, 2, 6, 1, 3, 5, 7]; the queue, list, tree nodes, and any uncached boxed values are normal JVM heap objects managed by GC.