Visiting Every Node: Pre, In and Post Order

Three orders, one tiny difference

To visit every node we go left and right recursively. The only question is when we handle the node itself: before, between, or after its children.

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

public class Main {
    static void preorder(TreeNode n, StringBuilder out) {
        if (n == null) return;
        out.append(n.value).append(' ');
        preorder(n.left, out);
        preorder(n.right, out);
    }

    static void inorder(TreeNode n, StringBuilder out) {
        if (n == null) return;
        inorder(n.left, out);
        out.append(n.value).append(' ');
        inorder(n.right, out);
    }

    static void postorder(TreeNode n, StringBuilder out) {
        if (n == null) return;
        postorder(n.left, out);
        postorder(n.right, out);
        out.append(n.value).append(' ');
    }

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

        StringBuilder a = new StringBuilder(), b = new StringBuilder(), c = new StringBuilder();
        preorder(root, a);
        inorder(root, b);
        postorder(root, c);
        System.out.println("pre:  " + a);
        System.out.println("in:   " + b);
        System.out.println("post: " + c);
    }
}

Output

pre:  8 3 1 6 10 14 
in:   1 3 6 8 10 14 
post: 1 6 3 14 10 8 

Tip: Look at the inorder line: 1 3 6 8 10 14 is sorted! That's no accident – this tree follows the binary search tree rule you'll learn next module.