Pattern Guide
Iterative Tree & Graph Traversal
"DFS without recursion. Explicit stack for inorder, preorder, postorder, Morris."
Recursive tree traversal can cause stack overflow for deep trees (n > 10^4). Iterative versions use an explicit stack. Preorder: push right then left. Inorder: go left until null, process, go right. Postorder: reverse of modified preorder. Morris traversal: inorder in O(1) space by threading the tree. Iterative DFS on graphs: same stack-based approach.
Problems you can solve with this pattern
4 problems · click any to start solving
// Iterative inorder (left-root-right)
function inorderIterative(root) {
const result = [], stack = [];
let curr = root;
while (curr || stack.length) {
while (curr) { stack.push(curr); curr = curr.left; }
curr = stack.pop();
result.push(curr.val);
curr = curr.right;
}
return result;
}
// Iterative preorder (root-left-right)
function preorderIterative(root) {
if (!root) return [];
const result = [], stack = [root];
while (stack.length) {
const node = stack.pop();
result.push(node.val);
if (node.right) stack.push(node.right); // push right first (processed last)
if (node.left) stack.push(node.left);
}
return result;
}
// Iterative postorder (left-right-root)
function postorderIterative(root) {
if (!root) return [];
const result = [], stack = [root];
while (stack.length) {
const node = stack.pop();
result.unshift(node.val); // add to front
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}
return result; // reverse preorder (root-right-left) → postorder
}Iterative inorder (left-root-right): push nodes while going left; when null, pop, process, go right. Iterative preorder (root-left-right): push root; pop and process; push right then left child. Postorder: preorder but push left before right, reverse result. Morris inorder: use null right pointers as threads back to ancestor, no extra space.
// Iterative inorder (left-root-right)
function inorderIterative(root) {
const result = [], stack = [];
let curr = root;
while (curr || stack.length) {
while (curr) { stack.push(curr); curr = curr.left; }
curr = stack.pop();
result.push(curr.val);
curr = curr.right;
}
return result;
}
// Iterative preorder (root-left-right)
function preorderIterative(root) {
if (!root) return [];
const result = [], stack = [root];
while (stack.length) {
const node = stack.pop();
result.push(node.val);
if (node.right) stack.push(node.right); // push right first (processed last)
if (node.left) stack.push(node.left);
}
return result;
}
// Iterative postorder (left-right-root)
function postorderIterative(root) {
if (!root) return [];
const result = [], stack = [root];
while (stack.length) {
const node = stack.pop();
result.unshift(node.val); // add to front
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}
return result; // reverse preorder (root-right-left) → postorder
}- Preorder: push right then left (so left processed first)
- Inorder: go left until null, pop+process, go right
- Postorder: reverse modified preorder (push left then right, add to front)
- Level-order: use queue, process all nodes at each level
Morris traversal (O(1) space): Thread right pointers of inorder predecessors back to current node. Two passes per node — first visit sets thread, second visit uses it. Restores tree structure after traversal.
BST Iterator pattern: Lazy inorder traversal — only advance when next() called. Push left spine of right child after popping. Amortized O(1) per call.