Definition
- Preorder – visit the node, then traverse the left subtree, then the right subtree (node-left-right).
- Inorder – traverse the left subtree, visit the node, then traverse the right subtree (left-node-right).
- Postorder – traverse both subtrees, then visit the node (left-right-node).
- Recursive – each traversal is a three-line method with a null base case.
- Iterative – an explicit
ArrayDequestack replaces the JVM call stack, preventingStackOverflowErroron very tall trees. - BST property – inorder on a binary search tree produces sorted output.
Rajesh audits the National Bank of India org chart three ways. In preorder he writes a manager's name first, then audits their teams. In inorder he audits the left team fully, writes the manager, then audits the right team. In postorder he audits both teams completely before writing the manager last. Same chart, three orders, chosen depending on what the audit needs.
Understanding the Concepts
What are the three depth-first traversals?
All three visit every node exactly once by going as deep as possible before backtracking. They differ only in when the node itself is visited relative to its two subtrees. Preorder visits the node first, inorder visits it between the subtrees, and postorder visits it last.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class RecursiveTraversals {
static class TreeNode {
int val; TreeNode left, right;
TreeNode(int v) { val = v; }
}
static void preorder(TreeNode node, List<Integer> res) {
if (node == null) return;
res.add(node.val); // visit
preorder(node.left, res); // left
preorder(node.right, res); // right
}
static void inorder(TreeNode node, List<Integer> res) {
if (node == null) return;
inorder(node.left, res); // left
res.add(node.val); // visit
inorder(node.right, res); // right
}
static void postorder(TreeNode node, List<Integer> res) {
if (node == null) return;
postorder(node.left, res); // left
postorder(node.right, res); // right
res.add(node.val); // visit
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
List<Integer> pre = new ArrayList<>(), in = new ArrayList<>(), post = new ArrayList<>();
preorder(root, pre); inorder(root, in); postorder(root, post);
System.out.println("Preorder: " + pre);
System.out.println("Inorder: " + in);
System.out.println("Postorder: " + post);
}
}
Preorder: [1, 2, 4, 5, 3]
Inorder: [4, 2, 5, 1, 3]
Postorder: [4, 5, 2, 3, 1]
Why do we need iterative versions?
Recursion uses the JVM call stack implicitly. On a very tall tree, deep recursion can cause StackOverflowError. The iterative versions use an explicit ArrayDeque stack allocated on the heap, which can grow as large as available memory. This makes them safe for production use on trees of any height.
package com.bank.core;
public class WhyIterative {
public static void main(String[] args) {
System.out.println("Recursive: uses JVM call stack (default ~512KB-1MB)");
System.out.println("Tall tree (100K nodes deep): StackOverflowError");
System.out.println("Iterative: uses heap-allocated ArrayDeque");
System.out.println("Can handle trees of any height");
}
}
Recursive: uses JVM call stack (default ~512KB-1MB)
Tall tree (100K nodes deep): StackOverflowError
Iterative: uses heap-allocated ArrayDeque
Can handle trees of any height
How does iterative preorder work?
Push the root onto the stack. Pop a node, visit it, then push its right child before its left child. Because the stack is LIFO, the left child will be processed first, which gives the correct node-left-right order.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class IterativePreorder {
static class TreeNode {
int val; TreeNode left, right;
TreeNode(int v) { val = v; }
}
public static List<Integer> preorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null) stack.push(node.right); // right first
if (node.left != null) stack.push(node.left); // left on top
}
return result;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
System.out.println("Iterative preorder: " + preorder(root));
}
}
Iterative preorder: [1, 2, 4, 5, 3]
How does iterative inorder work?
Keep a current pointer and a stack. Push nodes as you go left. When you cannot go further left, pop a node, visit it, then move to its right child. This simulates the left-node-right order exactly.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class IterativeInorder {
static class TreeNode {
int val; TreeNode left, right;
TreeNode(int v) { val = v; }
}
public static List<Integer> inorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
result.add(curr.val);
curr = curr.right;
}
return result;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
System.out.println("Iterative inorder: " + inorder(root));
}
}
Iterative inorder: [4, 2, 5, 1, 3]
How does iterative postorder work?
The cleanest trick is to do a modified preorder that visits node-right-left, then reverse the result to get left-right-node (postorder). The modified preorder pushes left before right instead of right before left.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
public class IterativePostorder {
static class TreeNode {
int val; TreeNode left, right;
TreeNode(int v) { val = v; }
}
public static List<Integer> postorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (node.left != null) stack.push(node.left); // left first
if (node.right != null) stack.push(node.right); // right on top
}
Collections.reverse(result); // node-right-left reversed = left-right-node
return result;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
System.out.println("Iterative postorder: " + postorder(root));
}
}
Iterative postorder: [4, 5, 2, 3, 1]
Why is inorder special for BSTs?
Inorder traversal of a binary search tree produces the values in sorted ascending order. This property makes inorder the natural choice for BST validation, kth-smallest-element, and range queries. If the inorder output is not sorted, the tree is not a valid BST.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class BstInorderSorted {
static class TreeNode {
int val; TreeNode left, right;
TreeNode(int v) { val = v; }
}
public static void main(String[] args) {
// BST: 5
// / \
// 3 7
// / \ \
// 2 4 8
TreeNode root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(7);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.right = new TreeNode(8);
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) { stack.push(curr); curr = curr.left; }
curr = stack.pop();
result.add(curr.val);
curr = curr.right;
}
System.out.println("BST inorder (sorted): " + result);
}
}
BST inorder (sorted): [2, 3, 4, 5, 7, 8]
What about time and space complexity?
All six implementations (3 recursive, 3 iterative) are O(n) time because each node is visited exactly once. Space is O(h) where h is the height of the tree, for the stack (implicit or explicit). For a balanced tree h is log n; for a skewed tree h is n.
package com.bank.core;
public class TraversalComplexity {
public static void main(String[] args) {
System.out.println("Time: O(n) for all six versions");
System.out.println("Space: O(h) where h = tree height");
System.out.println(" Balanced: h = log n");
System.out.println(" Skewed: h = n");
}
}
Time: O(n) for all six versions
Space: O(h) where h = tree height
Balanced: h = log n
Skewed: h = n
How is this applied in banking?
At the National Bank of India, I used these traversals on a fee expression tree. Preorder gave a prefix export for a downstream system. Inorder reconstructed the human-readable infix formula for display. Postorder produced exactly the token order that a stack-based evaluator consumes. The iterative versions were kept alongside the recursive ones for production safety on deep expression trees.
package com.bank.service;
public class FeeExpressionTree {
public static void main(String[] args) {
// Expression tree for: (base + tax) * rate
// *
// / \
// + rate
// / \
// base tax
System.out.println("Preorder (prefix): * + base tax rate");
System.out.println("Inorder (infix): base + tax * rate");
System.out.println("Postorder (postfix): base tax + rate *");
System.out.println("Postfix feeds directly into the stack evaluator");
}
}
Preorder (prefix): * + base tax rate
Inorder (infix): base + tax * rate
Postorder (postfix): base tax + rate *
Postfix feeds directly into the stack evaluator
What should a senior engineer know?
Morris traversal achieves O(1) space by temporarily threading the tree using right pointers, visiting each node without a stack or recursion. It is rarely used in production because it mutates the tree temporarily, but it demonstrates deep understanding of tree structure. Another senior point is that iterative postorder without the reverse trick requires tracking whether the right subtree has been visited, which is more complex but avoids the O(n) reversal.
package com.bank.core;
public class SeniorTraversalNotes {
public static void main(String[] args) {
System.out.println("Morris traversal: O(1) space, threads tree temporarily");
System.out.println("True iterative postorder: uses prev-pointer, no reverse");
System.out.println("Inorder on BST = sorted order (key property)");
System.out.println("All six versions: O(n) time, O(h) space");
}
}
Morris traversal: O(1) space, threads tree temporarily
True iterative postorder: uses prev-pointer, no reverse
Inorder on BST = sorted order (key property)
All six versions: O(n) time, O(h) space
Visual Overview
Tree: 1
/ \
2 3
/ \
4 5
Preorder (node-left-right): 1 → 2 → 4 → 5 → 3
Inorder (left-node-right): 4 → 2 → 5 → 1 → 3
Postorder (left-right-node): 4 → 5 → 2 → 3 → 1
Iterative Inorder Stack Walk ──────────────────────────── curr=1: push 1, go left curr=2: push 2, go left curr=4: push 4, go left curr=null: pop 4 → visit 4, go right (null) pop 2 → visit 2, go right (5) curr=5: push 5, go left (null) pop 5 → visit 5, go right (null) pop 1 → visit 1, go right (3) curr=3: push 3, go left (null) pop 3 → visit 3, go right (null) Stack empty + curr null → done Output: [4, 2, 5, 1, 3]
Key Takeaway
The three depth-first traversals differ only in when the node is visited relative to its children. Preorder visits first, inorder visits between, and postorder visits last. The recursive forms are trivially clear, but the iterative forms matter in production because they avoid StackOverflowError on very tall trees by using an explicit heap-allocated stack.
Iterative preorder pushes root, pops and visits, then pushes right before left so left is processed first. Iterative inorder goes left pushing nodes, pops and visits, then moves right. Iterative postorder uses the reverse trick: run node-right-left and reverse the result to get left-right-node. All six versions are O(n) time and O(h) space.
The single most important property to remember is that inorder on a binary search tree yields sorted output. This makes inorder the natural traversal for BST validation, kth-smallest, and range queries. Recognizing this connection is what interviewers look for.
In my project at the National Bank of India, I used these on a fee expression tree. Preorder gave prefix export, inorder gave human-readable infix display, and postorder gave exactly the token order for the stack-based evaluator. The iterative versions ran in production to handle arbitrarily deep formula trees safely.
Remember one sentence: preorder is node-left-right, inorder is left-node-right, postorder is left-right-node, and the iterative versions replace the call stack with an explicit stack for safety.
---