Inorder, Preorder, Postorder — Stack Overflow in Production

Every time your IDE folds or unfolds a directory, every time a compiler evaluates an expression like 3 + (4 * 2), and every time a database engine builds a query plan — a tree traversal is running under the hood. These aren't academic exercises; they're the backbone of tools you use every day. Understanding traversals is what separates developers who can reason about recursive structures from those who just copy-paste solutions and hope for the best.

The problem traversals solve is deceptively simple: a tree has no 'natural' reading order the way an array does. Arrays are linear — element 0, then 1, then 2. Trees branch. You need a deliberate strategy for visiting every node exactly once without missing any or doubling back. The three classical strategies — preorder, inorder, and postorder — each prioritise a different relationship between a node and its children, and that priority determines what the output is useful for.

By the end of this article you'll know not just how to implement all three traversals recursively and iteratively in Java, but — more importantly — you'll know which one to reach for when solving a real problem. You'll be able to look at a coding challenge and immediately say 'this needs postorder because I have to process children before parents' rather than guessing. That intuition is what interviewers are actually testing.

Tree Traversal Algorithms — Plain English and Rules

A binary tree traversal visits every node exactly once. There are four main orders:

Inorder (Left, Root, Right): Visit the left subtree, then the current node, then the right subtree. For a Binary Search Tree, inorder traversal produces elements in sorted ascending order — this is its most important property.

Preorder (Root, Left, Right): Visit the current node first, then recurse into left, then right. Used to create a copy of the tree or serialize it to a flat list.

Postorder (Left, Right, Root): Visit both subtrees before the current node. Used to delete a tree (process children before parent) or evaluate expression trees.

Level-order (BFS): Visit nodes level by level from top to bottom, left to right. Uses a queue, not recursion. Used to find tree height, check if balanced, or serialize by level.

Memory trick: the prefix tells you when the Root is visited relative to children: Pre-order = Root first. In-order = Root in between (2nd). Post-order = Root last.

Worked Example — All Four Traversals on the Same Tree

Tree: 1 / \ 2 3 / \ 4 5

Inorder (L-Root-R): Go left from 1 -> 2 -> 4. 4 has no children. Visit 4. Back to 2. Visit 2. Go right: visit 5. Back to 1. Visit 1. Go right: visit 3. Result: [4, 2, 5, 1, 3]

Preorder (Root-L-R): Visit 1. Go left: visit 2. Go left: visit 4. Back to 2. Go right: visit 5. Back to 1. Go right: visit 3. Result: [1, 2, 4, 5, 3]

Postorder (L-R-Root): Go left from 1 to 2 to 4. Visit 4. Back to 2. Go right to 5. Visit 5. Visit 2. Back to 1. Go right: visit 3. Visit 1. Result: [4, 5, 2, 3, 1]

Level-order (BFS): Level 0: visit 1. Level 1: visit 2, 3. Level 2: visit 4, 5. Result: [1, 2, 3, 4, 5]

The Anatomy of a Traversal: Depth-First Search (DFS) Strategies

In a Depth-First Search, we explore as far as possible along each branch before backtracking. The difference between the three types is simply when you 'visit' (process) the current node relative to its subtrees.

• Preorder (Root, Left, Right): Visit the parent before the children. Perfect for cloning trees or prefix notation.
• Inorder (Left, Root, Right): Visit the left child, then the parent, then the right. On a Binary Search Tree (BST), this results in sorted order.
• Postorder (Left, Right, Root): Visit the children before the parent. Essential for deleting nodes or calculating directory sizes where you need the sum of children first.

package io.thecodeforge.dsa;

class Node {
    int data;
    Node left, right;
    public Node(int item) { data = item; }
}

public class TreeTraversal {
    // Inorder: Left -> Root -> Right
    public void printInorder(Node node) {
        if (node == null) return;
        printInorder(node.left);
        System.out.print(node.data + " ");
        printInorder(node.right);
    }

    // Preorder: Root -> Left -> Right
    public void printPreorder(Node node) {
        if (node == null) return;
        System.out.print(node.data + " ");
        printPreorder(node.left);
        printPreorder(node.right);
    }

    // Postorder: Left -> Right -> Root
    public void printPostorder(Node node) {
        if (node == null) return;
        printPostorder(node.left);
        printPostorder(node.right);
        System.out.print(node.data + " ");
    }
}

Iterative Implementation — Explicit Stack for Production Safety

Iterative traversals eliminate recursion depth risks. They use a stack data structure (ArrayDeque for performance) to simulate the call stack manually. The pattern: push nodes onto stack in reverse order of visitation, pop, visit, then push children accordingly.

Inorder iterative: - Use a pointer curr starting at root. - While curr != null or stack not empty: - Push curr and all its left children onto stack. - Pop node, visit it. - Set curr = node.right.

Preorder iterative: - Push root onto stack. - While stack not empty: - Pop node, visit it. - Push right child first, then left (so left is popped next).

Postorder iterative: - Use two stacks, or one stack with a 'last visited' pointer. - Two-stack approach: push root to stack1. Pop from stack1, push to stack2. Push left then right to stack1. After processing, stack2 holds postorder.

package io.thecodeforge.dsa;

import java.util.ArrayDeque;
import java.util.Deque;

public class IterativeTraversal {
    public void inOrder(Node root) {
        Deque<Node> stack = new ArrayDeque<>();
        Node curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            System.out.print(curr.data + " ");
            curr = curr.right;
        }
    }

    public void preOrder(Node root) {
        if (root == null) return;
        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.print(node.data + " ");
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
    }

    public void postOrderTwoStacks(Node root) {
        if (root == null) return;
        Deque<Node> stack1 = new ArrayDeque<>();
        Deque<Node> stack2 = new ArrayDeque<>();
        stack1.push(root);
        while (!stack1.isEmpty()) {
            Node node = stack1.pop();
            stack2.push(node);
            if (node.left != null) stack1.push(node.left);
            if (node.right != null) stack1.push(node.right);
        }
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().data + " ");
        }
    }
}

Real-World Use Cases — Compilers, Filesystems, and Beyond

Tree traversals are not just interview questions — they power real systems:

Expression Evaluation (Postorder): Compilers parse expressions like 3 + 4 2 into an Abstract Syntax Tree (AST). To evaluate, they use postorder traversal: compute children first, then combine at the parent. This gives 42=8, then 3+8=11.

Directory Size Calculation (Postorder): Your OS computes folder size by summing sizes of all files in subfolders first, then adding the folder's own size. That's a postorder traversal — children before parent.

Serialization/Cloning (Preorder): To serialize a tree to a flat list for storage or transmission, preorder records the root first, then left subtree, then right subtree. Deserialization rebuilds by reading root, then recursively building left/right.

BST Sorted Output (Inorder): Rendering a sorted list of database records that are stored in a B+ tree? The database engine uses inorder traversal to walk the leaf nodes in sorted order.

Auto-complete (Level-order + Trie): When you type in Google search, the trie (a multi-way tree) is traversed level-by-level to find words starting with the prefix.