Depth-First Traversals, Compared

One tree, eight implementations. Three recursive orders differ only in when you visit a node relative to its two recursive calls; five iterative versions make that call stack explicit — and postorder, the one order that visits after both children, takes three genuinely different tricks to get right without recursion.

1 — The three orders, recursively

Every recursive depth-first traversal is the same three lines in a different order: recurse left, recurse right, and visit — placed before both calls, between them, or after both. That single placement decision is the entire difference between preorder, inorder and postorder.

The same tree drives every visualiser on this page — a 6-node tree with one missing child (node 3 has no left child), just irregular enough to make the stack mechanics honest.

1.1 Preorder (recursive)

void preorder(TreeNode nd) {    if (nd == null) return;    visit(nd.val);    preorder(nd.left);    preorder(nd.right);}

1.2 Inorder (recursive)

void inorder(TreeNode nd) {    if (nd == null) return;    inorder(nd.left);    visit(nd.val);    inorder(nd.right);}

1.3 Postorder (recursive)

void postorder(TreeNode nd) {    if (nd == null) return;    postorder(nd.left);    postorder(nd.right);    visit(nd.val);}

Step all three to the same point and compare the call stack: at the moment node 2 is topmost, preorder has already visited it, inorder is about to, and postorder won't until both 4 and 5 have come and gone. Same stack shape, three different answers to "has this node been visited yet?"

2 — Making the stack explicit

Every recursive call is really just a push onto a stack the runtime manages for you. Preorder and inorder both visit a node no later than "on the way in, before its right subtree" — which means an explicit stack never has to remember whether a node's children are done. That's what makes these two the easy half of going iterative.

Each iterative code pane below has a small toggle at the top: Deque · live is the version driving the visualiser, using the modern Deque/ArrayDeque API; java.util.Stack swaps in a full reference implementation written against the older, synchronized java.util.Stack class — the version you're more likely to find in an older textbook or a cheat sheet, with its own variable-naming conventions (ans, node/curr/peek/prev). The algorithm is identical either way; only the API and naming differ.

2.1 Preorder (iterative)

Push a node, pop it, visit it immediately, then push its children right-before-left so the left one pops first. No lookahead of any kind is needed — the moment a node is popped, it's correct to visit it.

Deque<TreeNode> stack = new ArrayDeque<>();stack.push(root);while (!stack.isEmpty()) {    TreeNode nd = stack.pop();    result.add(nd.val);    if (nd.right != null) stack.push(nd.right);    if (nd.left  != null) stack.push(nd.left);}

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) return ans;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        ans.add(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return ans;
}

2.2 Inorder (iterative)

This is exactly the mechanics behind 173's BSTIterator: push the entire left spine before visiting anything, then pop, visit, and push the popped node's right spine. A node only gets visited once every node to its left is already behind it.

Deque<TreeNode> stack = new ArrayDeque<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {    while (cur != null) { stack.push(cur); cur = cur.left; }    cur = stack.pop();    result.add(cur.val);    cur = cur.right;}

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        ans.add(curr.val);
        curr = curr.right;
    }
    return ans;
}

3 — Iterative postorder, three ways

Postorder visits after both children. A plain stack pop can't know that: when a node comes off the stack, you can't yet tell whether its right subtree has been dealt with. Three different fixes exist, and they are not equally different from each other.

Two of the three "iterative postorder" tricks are the same trick. Computing a mirrored preorder — root, then right, then left — and reversing the whole sequence at the very end produces exact postorder, because reversing "root, right, left" gives "left, right, root". Whether that final reversal is done by dumping the mirrored sequence into a second stack and popping it (which reverses automatically, since a stack is LIFO) or by calling Collections.reverse() on a plain list, the underlying algorithm — and its traversal order — is identical. The one genuinely different technique is the third: a single stack with a lastVisited pointer that looks ahead before deciding whether to descend right or emit a node, with no reversal step anywhere.

3.1 Postorder — two stacks

The first stack drives a root-right-left walk; every node it pops gets pushed onto a second stack instead of an output list. Reading the second stack back out via pop() reverses that sequence for free.

Deque<TreeNode> s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>();s1.push(root);while (!s1.isEmpty()) {    TreeNode nd = s1.pop();    s2.push(nd);    if (nd.left  != null) s1.push(nd.left);    if (nd.right != null) s1.push(nd.right);}while (!s2.isEmpty()) result.add(s2.pop().val);

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) return ans;
    Stack<TreeNode> s1 = new Stack<>();
    Stack<TreeNode> s2 = new Stack<>();
    s1.push(root);
    while (!s1.isEmpty()) {
        TreeNode node = s1.pop();
        s2.push(node);
        if (node.left != null) s1.push(node.left);
        if (node.right != null) s1.push(node.right);
    }
    while (!s2.isEmpty()) ans.add(s2.pop().val);
    return ans;
}

3.2 Postorder — reverse preorder

The same idea with one stack instead of two: build the root-right-left sequence directly into the answer list, then reverse the whole list once, at the very end.

Deque<TreeNode> stack = new ArrayDeque<>();stack.push(root);while (!stack.isEmpty()) {    TreeNode nd = stack.pop();    result.add(nd.val);    if (nd.left  != null) stack.push(nd.left);    if (nd.right != null) stack.push(nd.right);}Collections.reverse(result);

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> ans = new LinkedList<>();
    if (root == null) return ans;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        ans.addFirst(node.val); // prepend instead of reversing at the end
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return ans;
}

Notice this is the exact same push order as iterative preorder in §2.1, with left and right swapped on the two push lines — that swap is what turns "root, left, right" into "root, right, left", and the single reverse() at the end is doing precisely the job the second stack did in §3.1.

3.3 Postorder — one stack, with a lookahead

The only approach that produces postorder in one true forward pass, with no mirrored order and no reversal. It walks the left spine like iterative inorder, but at each node it peeks before popping: if there's an unvisited right child, go there first; otherwise the node is truly finished, so emit it and pop.

Deque<TreeNode> stack = new ArrayDeque<>();TreeNode cur = root, lastVisited = null;while (cur != null || !stack.isEmpty()) {    if (cur != null) { stack.push(cur); cur = cur.left; }    else {        TreeNode peek = stack.peek();        if (peek.right != null && lastVisited != peek.right) {            cur = peek.right;        } else {            result.add(peek.val);            lastVisited = stack.pop();        }    }}

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    TreeNode prev = null;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        TreeNode peek = stack.peek();
        if (peek.right != null && prev != peek.right) {
            curr = peek.right;
        } else {
            ans.add(peek.val);
            prev = stack.pop();
        }
    }
    return ans;
}

Watch node 3: it gets pushed, has no left child so cur immediately becomes null, and the very next iteration peeks at 3 and finds a real, unvisited right child (6) — so it descends there instead of emitting 3. Only after 6 has been fully emitted and popped does peeking at 3 again find lastVisited == peek.right, which is the signal that 3 is finally, truly done.

4 — The full comparison

Every approach is O(n) time — the difference is entirely in space and in how many times the "reverse" trick shows up as an explicit extra structure. Only the one-stack-plus-lookahead postorder matches the O(h) space profile of the other four single-stack methods; the two reverse-based postorder methods pay for their simplicity with an O(n) second structure, whether that's a second stack or the output list being built one full traversal ahead of its final, reversed form.

5 — Reference implementations

// recursive
void preorder(TreeNode nd, List<Integer> result) {
    if (nd == null) return;
    result.add(nd.val);
    preorder(nd.left, result);
    preorder(nd.right, result);
}

// iterative
public List<Integer> preorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode nd = stack.pop();
        result.add(nd.val);
        if (nd.right != null) stack.push(nd.right);
        if (nd.left  != null) stack.push(nd.left);
    }
    return result;
}

// recursive
void inorder(TreeNode nd, List<Integer> result) {
    if (nd == null) return;
    inorder(nd.left, result);
    result.add(nd.val);
    inorder(nd.right, result);
}

// iterative
public List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        cur = stack.pop();
        result.add(cur.val);
        cur = cur.right;
    }
    return result;
}

// recursive
void postorder(TreeNode nd, List<Integer> result) {
    if (nd == null) return;
    postorder(nd.left, result);
    postorder(nd.right, result);
    result.add(nd.val);
}

// iterative — two stacks
public List<Integer> postorderTwoStacks(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Deque<TreeNode> s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>();
    s1.push(root);
    while (!s1.isEmpty()) {
        TreeNode nd = s1.pop();
        s2.push(nd);
        if (nd.left  != null) s1.push(nd.left);
        if (nd.right != null) s1.push(nd.right);
    }
    while (!s2.isEmpty()) result.add(s2.pop().val);
    return result;
}

// iterative — reverse of a mirrored preorder
public List<Integer> postorderReversePreorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode nd = stack.pop();
        result.add(nd.val);
        if (nd.left  != null) stack.push(nd.left);
        if (nd.right != null) stack.push(nd.right);
    }
    Collections.reverse(result);
    return result;
}

// iterative — one stack, with a lookahead
public List<Integer> postorderOneStack(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root, lastVisited = null;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            TreeNode peek = stack.peek();
            if (peek.right != null && lastVisited != peek.right) {
                cur = peek.right;
            } else {
                result.add(peek.val);
                lastVisited = stack.pop();
            }
        }
    }
    return result;
}