Definition
- Inorder – visit left subtree, then the node, then right subtree; produces sorted output on a BST.
- Preorder – visit the node first, then left, then right; used for cloning and serialisation.
- Postorder – visit left, then right, then the node last; used for deletion and expression evaluation.
- Level-order – visit nodes level by level using a queue; BFS traversal.
- Complexity – all traversals visit every node once, giving O(n) time and O(h) stack space for recursion.
Auditing the branch hierarchy at the National Bank of India requires different traversal orders for different reports. Inorder gives a sorted roster of account balances. Preorder gives a top-down export to replicate the hierarchy in a new branch. Postorder gives the safe shutdown order where every subordinate is closed before the manager.
Understanding the Concepts
What are the three depth-first traversals?
All three depth-first traversals visit the same tree. The only difference is when the current node is processed relative to the two recursive calls. This makes them variations of one template.
- Inorder: recurse left, visit node, recurse right.
- Preorder: visit node, recurse left, recurse right.
- Postorder: recurse left, recurse right, visit node.
package com.bank.service;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
public class HierarchyTraversalService {
static class AccountNode {
BigDecimal balance;
AccountNode left, right;
AccountNode(BigDecimal balance) { this.balance = balance; }
}
public static void inorder(AccountNode node, List<BigDecimal> result) {
if (node == null) return;
inorder(node.left, result);
result.add(node.balance);
inorder(node.right, result);
}
public static void preorder(AccountNode node, List<BigDecimal> result) {
if (node == null) return;
result.add(node.balance);
preorder(node.left, result);
preorder(node.right, result);
}
public static void postorder(AccountNode node, List<BigDecimal> result) {
if (node == null) return;
postorder(node.left, result);
postorder(node.right, result);
result.add(node.balance);
}
}
When do you use each traversal?
Each traversal order maps to a concrete use case. Knowing which order to use for which task is what interviewers look for.
- Inorder – sorted output from a BST. The left-node-right order follows the BST invariant and produces ascending values.
- Preorder – cloning or serialising a tree. The root is emitted first, so replaying a preorder sequence rebuilds the same shape.
- Postorder – safe deletion or expression evaluation. Children are handled before the parent, so you can free child nodes before the parent or compute operands before the operator.
- Level-order – printing by depth, finding shortest paths, connecting level siblings.
// Use case: inorder on BST produces sorted output
// 500
// / \
// 200 800
// / \
// 100 900
// Inorder: [100, 200, 500, 800, 900] - sorted!
How does the iterative inorder traversal work?
The iterative version uses an explicit stack to replace the call stack. Push all left children until null, then pop and visit, then move to the right child and repeat.
import java.util.Stack;
public static List<BigDecimal> inorderIterative(AccountNode root) {
List<BigDecimal> result = new ArrayList<>();
Stack<AccountNode> stack = new Stack<>();
AccountNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.add(current.balance);
current = current.right;
}
return result;
}
What is Morris Traversal?
Morris Traversal achieves inorder traversal in O(1) extra space by temporarily creating threads (links from a node's inorder predecessor back to it). It modifies the tree structure temporarily and restores it.
public static List<BigDecimal> morrisInorder(AccountNode root) {
List<BigDecimal> result = new ArrayList<>();
AccountNode current = root;
while (current != null) {
if (current.left == null) {
result.add(current.balance);
current = current.right;
} else {
// Find inorder predecessor
AccountNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
predecessor.right = current; // Create thread
current = current.left;
} else {
predecessor.right = null; // Remove thread
result.add(current.balance);
current = current.right;
}
}
}
return result;
}
// Time: O(n), Space: O(1) - no stack or recursion
How is recursive different from iterative traversal?
| Aspect | Recursive | Iterative (Stack) | Morris |
|---|---|---|---|
| Space | O(h) call stack | O(h) explicit stack | O(1) |
| Simplicity | Very simple | Moderate | Complex |
| Stack overflow risk | Yes, for deep trees | No | No |
| Modifies tree | No | No | Yes, temporarily |
| Production use | Default choice | Deep trees | Memory-constrained |
// Deep tree risk with recursion
// A skewed tree of 100,000 nodes causes StackOverflowError
// Iterative version handles any depth safely
What are the edge cases?
- Empty tree (null root) – all traversals return an empty list.
- Single node – all three traversals return just that node's value.
- Left-skewed tree – inorder and postorder visit nodes bottom-up; recursion depth equals n.
- Right-skewed tree – preorder visits nodes in the same order as insertion.
// Edge case: null root
List<BigDecimal> result = new ArrayList<>();
inorder(null, result);
System.out.println(result); // []
What are common mistakes?
The most common mistake is forgetting the null check at the start of the recursive method.
// WRONG: no null check
public static void inorderBuggy(AccountNode node, List<BigDecimal> result) {
inorderBuggy(node.left, result); // NullPointerException when node is null
result.add(node.balance);
inorderBuggy(node.right, result);
}
// CORRECT: null check first
public static void inorder(AccountNode node, List<BigDecimal> result) {
if (node == null) return;
inorder(node.left, result);
result.add(node.balance);
inorder(node.right, result);
}
What should a senior engineer know?
A senior engineer should be able to implement all three traversals both recursively and iteratively, and explain Morris traversal's threading mechanism. They should know that preorder plus inorder (or postorder plus inorder) uniquely determines a binary tree, which is how serialisation and reconstruction work.
They should also know that the iterative preorder is the simplest (push right then left to the stack), iterative inorder requires the "push all lefts" pattern, and iterative postorder is the trickiest (use a prev pointer or two stacks).
Visual Overview
Tree: 50
/ \
20 80
/ \ \
10 30 90
Inorder (L, N, R): 10 -> 20 -> 30 -> 50 -> 80 -> 90 (sorted!)
Preorder (N, L, R): 50 -> 20 -> 10 -> 30 -> 80 -> 90 (top-down)
Postorder(L, R, N): 10 -> 30 -> 20 -> 90 -> 80 -> 50 (bottom-up)
Traversal Template:
┌─────────────────────────────────────────────┐
│ void traverse(node): │
│ if node == null: return │
│ [PREORDER: visit(node)] │
│ traverse(node.left) │
│ [INORDER: visit(node)] │
│ traverse(node.right) │
│ [POSTORDER: visit(node)] │
└─────────────────────────────────────────────┘
Iterative Inorder (Stack):
┌───────────────────────────────┐
│ Push all lefts -> Pop -> Visit│
│ -> Move to right -> Repeat │
└───────────────────────────────┘
Stack: [50, 20, 10] -> pop 10 (visit) -> right=null
Stack: [50, 20] -> pop 20 (visit) -> right=30
Stack: [50, 30] -> pop 30 (visit) -> right=null
Stack: [50] -> pop 50 (visit) -> right=80
...
Key Takeaway
Traversing a binary tree means visiting every node exactly once, and the three depth-first traversals differ only in when the current node is visited relative to its subtrees. Inorder visits left, then node, then right, and on a BST this produces sorted ascending output. Preorder visits the node first, then left, then right, making it the choice for cloning and serialisation. Postorder visits left, right, then node, making it the choice for safe deletion and expression evaluation.
The key interview insight is that each traversal order maps to a real use case. Inorder for sorted output, preorder for copy/serialize, postorder for teardown/evaluate, and level-order for breadth-first views. Being able to name the use case for each order shows understanding beyond memorisation.
At the National Bank of India, the product-approval hierarchy was stored as a tree. Inorder gave a sorted roster of approval amounts. Preorder gave a top-down export to replicate the hierarchy in a new branch. Postorder gave the safe decommissioning order. The same tree produced all three reports by changing only the position of the visit statement.
The senior-level nuances are the iterative versions and Morris traversal. Deep trees can overflow the call stack, so the iterative versions using an explicit stack handle any depth safely. Morris traversal achieves O(1) space by temporarily threading the tree, which matters in memory-constrained environments. Knowing that preorder plus inorder uniquely determines a binary tree is the basis of tree serialisation.
Remember one sentence: The three traversals differ only in the position of the visit statement relative to the recursive calls, and each order maps to a concrete use case: inorder for sorted output, preorder for cloning, postorder for deletion.
---