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.

Basic Implementation

Basic.java

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); }
}

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.

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