Preorder Traversal

Visit the root before each subtree, producing root-left-right order.

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.

preorder Preorder records the current node before visiting left and right subtrees.

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)));
    }
    static void preorder(Node node, List<Integer> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }
    public static void main(String[] args) { List<Integer> output = new ArrayList<>(); preorder(sampleTree(), output); System.out.println(output); }
}

                        
1tree ← 4(2(1,3),6(5,7)), output ← []1import java.util.*;⋯values this step4(2(1,3),6(5,7))tree[]output
2output ← [4]⋯18}19static void preorder(Node node, List<Integer> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }20public static void main(String[] args) { List<Integer> output = new ArrayList<>(); preorder(sampleTree(), output); System.out.println(output); }⋯values this step[] → [4]output4node
3output ← [4, 2]⋯18}19static void preorder(Node node, List<Integer> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }20public static void main(String[] args) { List<Integer> output = new ArrayList<>(); preorder(sampleTree(), output); System.out.println(output); }⋯values this step[4] → [4, 2]output2node
4output ← [4, 2, 1]⋯18}19static void preorder(Node node, List<Integer> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }20public static void main(String[] args) { List<Integer> output = new ArrayList<>(); preorder(sampleTree(), output); System.out.println(output); }⋯values this step[4, 2] → [4, 2, 1]output1node
5output ← [4, 2, 1, 3]⋯18}19static void preorder(Node node, List<Integer> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }20public static void main(String[] args) { List<Integer> output = new ArrayList<>(); preorder(sampleTree(), output); System.out.println(output); }⋯values this step[4, 2, 1] → [4, 2, 1, 3]output3node
6output ← [4, 2, 1, 3, 6]⋯18}19static void preorder(Node node, List<Integer> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }20public static void main(String[] args) { List<Integer> output = new ArrayList<>(); preorder(sampleTree(), output); System.out.println(output); }⋯values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node
7output ← [4, 2, 1, 3, 6, 5]⋯18}19static void preorder(Node node, List<Integer> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }20public static void main(String[] args) { List<Integer> output = new ArrayList<>(); preorder(sampleTree(), output); System.out.println(output); }⋯values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node
8output ← [4, 2, 1, 3, 6, 5, 7]⋯18}19static void preorder(Node node, List<Integer> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }20public static void main(String[] args) { List<Integer> output = new ArrayList<>(); preorder(sampleTree(), output); System.out.println(output); }⋯values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node
9public static void main(String[] args) { List<Integer> output = new Ar…⋯19    static void preorder(Node node, List<Integer> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }20    public static void main(String[] args) { List<Integer> output = new ArrayList<>(); preorder(sampleTree(), output); System.out.println(output); }21}values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

Time: O(n)
Space: O(h) recursion stack

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.
preorder(Node node, List<Integer> output) is recursive and returns void. The base case if (node == null) return; stops at missing child references.
Each non-null stack frame first mutates the shared ArrayList<Integer> with output.add(node.value), autoboxing through Integer.valueOf so these small fixture values may be cached Integer instances, then calls preorder(node.left, output) before preorder(node.right, output).
The replay-visible output grows in root-left-right order from [4] to [4, 2, 1, 3, 6, 5, 7]. The recursive calls use normal Java stack frames; the prebuilt tree, output list, and any uncached boxed values are heap objects managed by GC once unreachable.