Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Inorder = visit Left subtree, then the Node, then the Right subtree. Recursively it's three lines: recurse left, visit, recurse right. The iterative version uses an explicit stack: push all left children, pop-and-visit, then move to the right child of the popped node, and repeat. Both are O(n) time; recursion uses O(h) call-stack space, the iterative version O(h) explicit-stack space. On a BST, inorder yields the values in sorted ascending order.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can produce inorder both recursively and iteratively, and whether you know inorder on a BST yields sorted order.
Where candidates slip
Mixing up the order (visiting the node before recursing left), or in the iterative version pushing the right child before fully draining the left spine.
How to stand out
Write the recursion instantly, then offer the stack-based iterative version unprompted and connect it to Kth Smallest and Validate BST, which are inorder with extra state.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Inorder visits the node between its subtrees. Compare with preorder (node first) and postorder (node last).
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Recursive Inorder — Left, Node, Right
1Hint 1Explore hintHide hint
Inorder means the node is processed between its two subtrees. In what order do the three actions — recurse left, visit, recurse right — happen?
2Hint 2Explore hintHide hint
Write the base case first: a null node produces nothing, so just return.
3Hint 3Explore hintHide hint
For a real node: recurse left, then append/print the node's value, then recurse right. That literal translation IS the algorithm.
A · Core idea
Inorder is defined recursively: to traverse a node, fully traverse its left subtree, then visit the node, then fully traverse its right subtree.
The base case stops the descent. When recursion reaches a null pointer (the child of a leaf), there's nothing to visit, so it simply returns. This is what unwinds the recursion at the bottom of every branch.
Why the order matters. The single line that defines inorder is visiting the node between the two recursive calls. Move that visit before the left recursion and you get preorder; move it after the right recursion and you get postorder. The three traversals share identical structure and differ only in where the visit sits.
The BST payoff. In a binary search tree every left descendant is smaller and every right descendant is larger. Inorder therefore emits the smallest values first and the largest last — a sorted sequence — without any explicit sorting. That's why Validate BST, Kth Smallest, and Minimum Absolute Difference in a BST all reduce to 'do an inorder and watch the stream'.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [4,2,5,1,3]How to read it:Numbers in parentheses show the visit order: 1,2,3,4,5.
1 2 3 4 5C · Code with teaching comments
Reference implementation preview// Definition for a binary tree node. class Node { int data; Node left; Node right;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
All three DFS traversals are the same three statements — recurse left, visit, recurse right — reordered. Inorder puts the visit in the middle. Anchor on that and you never confuse the three again.
ComplexityO(n) time, O(h) space — Each node is visited exactly once and does O(1) work → O(n) time. The recursion stack is as deep as the tree height h → O(h) space (O(log n) balanced, O(n) skewed).
E · Edge cases and pitfalls6root = [1] — Left null, visit 1, right null → output '1'.Explore edge casesHide edge cases
Edge cases handled
root = [1]Left null, visit 1, right null → output '1'.Right-skewed chain 1→2→3No left subtrees → output '1 2 3'.Left-skewed chain 3→2→1Drills to the deepest left first → output '1 2 3'.
Pitfalls
- Visiting the node before recursing left — that produces preorder, not inorder.
- Forgetting the null base case — infinite recursion / null dereference.
- Recursing right before left — reverses the output.
Approach 2 of 2 · Optimal
Iterative Inorder — Explicit Stack
1Hint 1Explore hintHide hint
The call stack in the recursive version is really just remembering 'which nodes still need visiting after their left subtree'. Can you keep that memory in an explicit stack?
2Hint 2Explore hintHide hint
Maintain a pointer `cur` and a stack. Push every left child as you walk down the left spine until cur is null.
3Hint 3Explore hintHide hint
When you can't go left anymore, pop a node, visit it, then set cur to that node's right child and repeat the whole process.
A · Core idea
The recursion's call stack does exactly one thing: it remembers the chain of nodes whose left subtrees we've entered but whose own value we haven't yet printed. We can hold that chain in an explicit stack and reproduce inorder without recursion.
The two-phase loop. Keep a current pointer cur (start at root) and a stack. Phase one: while cur is non-null, push cur and move cur = cur.left — this walks the left spine, stacking ancestors. When cur becomes null we've gone as far left as possible. Phase two: pop a node, visit it (its entire left subtree is already done), then set cur = popped.right to explore that node's right subtree. Loop until both the stack is empty and cur is null.
Why visit on pop, not on push. A node's value may only be emitted after its left subtree is fully visited. Pushing records 'I owe this node a visit later'; popping is the moment its left side is finished, so that's when we print and then pivot to its right child.
Termination. The loop continues while cur != null OR stack is non-empty. The cur != null half handles descending into a right subtree that exists even when the stack momentarily empties; the stack half handles backing up to ancestors.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [4,2,5,1,3]How to read it:Push the left spine (4,2,1), then pop-visit and pivot right repeatedly.
1 2 3 4 5C · Code with teaching comments
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
An explicit stack is just a manual call stack. 'Push the left spine, pop-visit, go right' is the reusable inorder skeleton — bolt on a counter and it becomes Kth Smallest in BST; track the previous value and it becomes Validate BST.
ComplexityO(n) time, O(h) space — Each node is pushed once and popped once → O(n) time. The stack holds at most one root-to-leaf path of left ancestors → O(h) space.
E · Edge cases and pitfalls6root = [1] — Push 1, pop-visit 1, right null, stack empty → '1'.Explore edge casesHide edge cases
Edge cases handled
root = [1]Push 1, pop-visit 1, right null, stack empty → '1'.Right-skewed chain 1→2→3Each node pushed and immediately popped (no left children) → '1 2 3'.Left-skewed chain 3→2→1Whole spine pushed first, then popped in reverse → '1 2 3'.
Pitfalls
- Visiting on push instead of on pop — emits the node before its left subtree.
- Forgetting the `cur != null` half of the loop condition — drops right subtrees that exist when the stack is empty.
- Not pivoting to cur.right after the pop — the right subtree is never explored.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic void inorder(Node root) { Deque<Node> stack = new ArrayDeque<>(); Node cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { // push the entire left spineExplore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Wrong visit position (preorder by accident)
Inorder requires the node to be printed BETWEEN the two recursions. Printing before the left recursion produces preorder output.
Explore the code comparisonHide the code comparison
Wrong visit position (preorder by accident)
Inorder requires the node to be printed BETWEEN the two recursions. Printing before the left recursion produces preorder output.
Don't write this
def inorder(root):
if root is None:
return
print(root.data, end=' ') # too early -> preorder
inorder(root.left)
inorder(root.right)Write this instead
def inorder(root):
if root is None:
return
inorder(root.left)
print(root.data, end=' ') # between subtrees -> inorder
inorder(root.right)2Iterative version visits on push
A node may only be visited after its full left subtree. Printing when you push means the node is emitted before its left descendants.
Explore the code comparisonHide the code comparison
Iterative version visits on push
A node may only be visited after its full left subtree. Printing when you push means the node is emitted before its left descendants.
Don't write this
while (cur != null) {
System.out.print(cur.data + " "); // visited too early
stack.push(cur);
cur = cur.left;
}Write this instead
while (cur != null) {
stack.push(cur); // remember for later
cur = cur.left;
}
cur = stack.pop();
System.out.print(cur.data + " "); // visit when left subtree is doneRevise
Carry the pattern into the interview
Pattern to remember
Depth-first traversal in Left → Node → Right order
Code pattern to memorize
inorder(node):
if node is null: return
inorder(node.left)
visit(node)
inorder(node.right)Rules to remember
- 1Order is Left, Node, Right — the node is visited between its two subtrees.
- 2On a BST, inorder prints values in ascending sorted order — the signature use case.
- 3Iterative: push left spine, pop-and-visit, then descend into the popped node's right child.
- 4The base case (null → return) is what stops the recursion at the bottom of each branch.
- 5'Inorder' refers to when the node is visited relative to its children — middle for inorder, first for preorder, last for postorder.
Use this pattern when
- You need a BST's elements in sorted order without an explicit sort
- Validating a BST, finding the kth smallest, or minimum absolute difference
- Any traversal where the node belongs logically between its subtrees
Choose another pattern when
- You need root-first processing (e.g. cloning, serializing top-down) → preorder
- You need children-before-parent (e.g. freeing nodes, computing height) → postorder
- You need level-by-level output → BFS level order
Interview takeaway
Inorder is the traversal that 'unrolls' a BST into sorted order. Master both the three-line recursion and the push-left-spine / pop / go-right stack version — the iterative form is the template for Kth Smallest in BST and BST validation.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternInorder DFS (Left → Node → Right). The recursion is one of three traversals that differ only in where the visit sits; the iterative stack version (push left spine, pop-visit, go right) is the reusable template behind Kth Smallest in BST and BST validation. On a BST, inorder is sorted order.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Tree: Preorder TraversalSame structure; move the visit BEFORE the left recursion (Node, Left, Right).
- Tree: Postorder TraversalMove the visit AFTER the right recursion (Left, Right, Node).
- Kth Smallest Element in a BSTIterative inorder, stop after popping the kth node.
- Validate Binary Search TreeInorder must be strictly increasing — track the previous value during the traversal.