DFS traversals (preorder/inorder/postorder) — recursive and iterative.

Problem. Implement the three depth-first traversals of a binary tree — preorder, inorder, postorder — both recursively and iteratively.

The idea

All three DFS orders visit the same nodes; they differ only in when the current node is emitted relative to descending into its children:

• Preorder — emit, go left, go right (node, L, R).
• Inorder — go left, emit, go right (L, node, R). On a BST this is sorted order.
• Postorder — go left, go right, emit (L, R, node).

Recursive — O(n) time, O(h) space

The recursion mirrors the definition exactly; the call stack carries O(h) frames. The only thing that moves between variants is the position of the visit line.

void preorder(TreeNode n, List<Integer> out) {
    if (n == null) return;
    out.add(n.val);          // visit
    preorder(n.left, out);
    preorder(n.right, out);
}

void inorder(TreeNode n, List<Integer> out) {
    if (n == null) return;
    inorder(n.left, out);
    out.add(n.val);          // visit
    inorder(n.right, out);
}

void postorder(TreeNode n, List<Integer> out) {
    if (n == null) return;
    postorder(n.left, out);
    postorder(n.right, out);
    out.add(n.val);          // visit
}

Iterative — O(n) time, O(h) space

Recursion just hides an explicit stack, so we can make it explicit. Preorder is the cleanest: push the node, pop and emit, then push right before left so left comes off first.

List<Integer> preorderIter(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode n = stack.pop();
        out.add(n.val);
        if (n.right != null) stack.push(n.right);  // pushed first -> popped last
        if (n.left  != null) stack.push(n.left);
    }
    return out;
}

Inorder walks left as far as possible, pushing each node, then pops/emits and pivots right:

List<Integer> inorderIter(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }  // dive left
        cur = stack.pop();
        out.add(cur.val);          // visit on the way up
        cur = cur.right;           // then go right
    }
    return out;
}

Postorder is trickiest. The neat trick: run a modified preorder (node, right, left) and reverse the result — that yields (left, right, node).

List<Integer> postorderIter(TreeNode root) {
    LinkedList<Integer> out = new LinkedList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode n = stack.pop();
        out.addFirst(n.val);       // reverse-preorder: prepend
        if (n.left  != null) stack.push(n.left);
        if (n.right != null) stack.push(n.right);
    }
    return out;
}