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.

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

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.

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