Tree Traversals in Java — Inorder, Preorder, Postorder (Recursive and Iterative)

Three DFS tree traversals

Preorder (Root, Left, Right)

• Visit node first
• Recurse left, then right

Inorder (Left, Root, Right)

• Recurse left first
• Visit node
• Recurse right

Postorder (Left, Right, Root)

• Recurse left, then right
• Visit node last

Mnemonic: name says when ROOT is visited.

• Pre = before children
• In = between left and right
• Post = after children

Recursive form (clean and natural)

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

• Time: O(n)
• Space: O(h) recursion stack

Iterative preorder

• Use Deque (ArrayDeque, not legacy Stack)
• Push root
• Loop: pop, visit, push right FIRST, then left
• (LIFO: left pops first)

Iterative inorder

• Walk left, push each node
• When null, pop and visit
• Move to right child of popped
• Repeat

Iterative postorder — trickier

Approach 1: Two stacks

• Modified preorder: Root, Right, Left
• Push to output stack (reversed)
• Pop output → postorder

Approach 2: Single stack with visited tracking

• Peek top
• If has unvisited right, descend
• Else visit and pop
• Track lastVisited to avoid re-descending

Use cases for each order

Preorder

• Copy tree (root before children)
• Serialize tree
• Prefix expression
• DFS path enumeration

Inorder

• BST sorted output (THE key property)
• Validate BST (should be strictly increasing)
• K-th smallest in BST
• Infix expression printing

Postorder

• Delete tree (free children first)
• Evaluate postfix
• Compute height (need children's heights)
• Compute aggregates (sum, count)
• Topological sort (reverse postorder of DAG)

Level-order (BFS)

• Not DFS, uses queue
• Level-by-level
• Shortest path in unweighted tree

Morris traversal — O(1) space

• Thread the tree temporarily
• For each node with left child, find rightmost in left subtree (predecessor)
• Set pred.right = current to create thread
• On revisit, restore and visit
• Time O(n), space O(1)
• Modifies tree temporarily; not thread-safe
• Advanced; mention in interviews if relevant

Common bugs

1. Wrong iterative push order

• Iterative preorder: push RIGHT first, then LEFT
• Stack is LIFO; left pops first
• Common mistake: push left then right → wrong order

2. Confusing inorder and preorder

• Practice all three until automatic

3. Not handling null

• Recursive: if (node == null) return;
• Iterative: check before pushing

4. Iterative postorder errors

• Forgetting visited tracking → infinite loop
• Two-stack version is easier; use it if approach 2 is shaky

5. Stack overflow on deep trees

• JVM default ~10K-50K stack frames
• Skewed BST or linked-list tree can overflow
• Use iterative or Morris

6. Using legacy Stack class

• Synchronized, slow
• Use ArrayDeque

Interviews — what to know

Recursive: all 3, cold Iterative inorder: walk-left-push pattern Iterative preorder: pop, push right then left Iterative postorder: two-stack trick (or single-stack with visited) Use cases: in-order for BSTs, post-order for deletion BFS: queue-based, level-by-level Morris: O(1) space, advanced

Practical tip

Use recursion unless trees are very deep or you're avoiding stack overhead.

Use iterative for production code on user-supplied data (deep trees possible).

Use Morris only when O(1) space is critical and tree mutation is acceptable.

Recommendation: Master all three DFS traversals in both recursive and iterative forms. The recursive versions are short and natural — the order in the name (pre/in/post) tells you when the root is visited relative to children. Use them unless you have very deep trees (>10K depth) where stack overflow is a risk. The iterative versions use an explicit Deque (use `ArrayDeque`, not the legacy Stack class). Iterative preorder is the simplest — push root, then pop-visit-push-right-then-left (right first because the stack is LIFO and left should pop first). Iterative inorder uses a walk-left-push-then-pop pattern. Iterative postorder is the trickiest — the cleanest approach is to do a modified preorder (Root, Right, Left) pushing to an output stack, then pop the output stack to get the postorder. Know the use cases: inorder for BSTs (yields sorted output, validates BSTs, finds K-th smallest), postorder for deletion and aggregates (need children processed before parent), preorder for copying and serialization. Mention level-order (BFS) with a queue for completeness. For senior interviews, know Morris traversal — O(n) time, O(1) extra space by temporarily threading the tree. The mental model: DFS = recursive descent + visit at one of three points; iterative = explicit stack mimicking the call stack. Always handle null, choose ArrayDeque over Stack, and prefer recursive unless depth is a concern.