Pattern Reference
Iterative Tree Traversal
"Morris traversal, stack-based pre/in/post-order without recursion."
Loading...
Deep Dive Tutorial
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, preorder, and postorder
// 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
}Worked Problems
repeat
Iterative traversal patterns:
- 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.
- 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.