Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Visit every node in a fixed order. Preorder = node, left, right; inorder = left, node, right; postorder = left, right, node. The recursive form is three lines — just move the `visit(node)` call relative to the two recursive calls. The interview-grade follow-up is the iterative inorder using an explicit stack (O(h) space), and the brag-worthy O(1)-space answer is Morris traversal via threaded links.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can write a clean recursive tree walk, explain the difference between the three orders, and convert the recursion into an explicit-stack iterative version on request.
Where candidates slip
Mixing up inorder vs preorder ordering, forgetting the null base case, or being unable to produce the iterative version when the interviewer says 'now do it without recursion'.
How to stand out
Name what each order is good for (preorder copies, postorder aggregates, inorder sorts a BST), then offer Morris traversal for O(1) space to show you know recursion isn't the only tool.
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 approachFirst decision previewNeed to visit every nodeGroup nodes by level?YesNoExplore the full treeCollapse the tree
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 DFS — All Three Orders
1Hint 1Explore hintHide hint
A binary tree is recursive by definition: every node's left and right children are themselves binary trees. What's the simplest function that processes a node and then calls itself on the children?
2Hint 2Explore hintHide hint
Write a helper that takes a node, returns immediately if it's null (base case), then makes a recursive call on left and right with a `visit` step somewhere in between.
3Hint 3Explore hintHide hint
To switch between preorder, inorder, and postorder, you only move the single line that records `node.val` — before both recursive calls, between them, or after both.
A · Core idea
A binary tree is defined recursively — a node plus a left subtree plus a right subtree — so the most natural traversal is itself recursive. The helper does exactly three things in some order: process the current node, recurse left, recurse right.
The base case comes first. Before touching node.val or its children, return immediately when node is null. An empty subtree contributes nothing to the traversal, and checking this first is what stops you from dereferencing a missing child.
The three orders are one template. Preorder records the value before descending (node, left, right); inorder records it between the two descents (left, node, right); postorder records it after both (left, right, node). That single moved line is the entire conceptual difference — interviewers love asking you to convert one to another precisely because it tests whether you understand the structure rather than memorized one snippet.
Why each order exists. Preorder visits a parent before its children, which is the order you need to copy or serialize a tree top-down. Postorder visits children before the parent, which is required whenever a node's answer depends on its subtrees — computing heights, deleting a tree, or bottom-up DP. Inorder on a binary search tree emits values in sorted ascending order, the property behind Validate BST, Kth Smallest, and in-order successors.
Why O(n) is optimal. You must look at every node to produce its value, so no traversal can beat linear time. The only thing you can optimize is the space — and that's exactly what the iterative and Morris variants attack.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,null,2,3] (1's right child is 2; 2's left child is 3)How to read it:Inorder walks left-node-right: 1 (no left) → into right subtree → 3 then 2 → output [1,3,2].
[1,3,2]C · Code with teaching comments
Reference implementation preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode 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
Don't memorize three separate functions — memorize one template and remember that the position of the visit line is the whole story. "Pre/in/post" literally describes when you visit relative to the recursion: PRE-before, IN-between, POST-after.
ComplexityO(n) time, O(h) space — Each of the n nodes is visited exactly once → O(n) time. The recursion depth equals the tree height h, so the call stack uses O(h) space — O(log n) for a balanced tree, O(n) for a degenerate (linked-list-shaped) tree.
E · Edge cases and pitfalls3Forgetting the null base case — recursing into a null child throws a NullPointerException / AttributeError.Explore edge casesHide edge cases
Pitfalls
- Forgetting the null base case — recursing into a null child throws a NullPointerException / AttributeError.
- Placing the visit line in the wrong spot and silently returning preorder when inorder was asked.
- Building the result list as a return value and concatenating at every node — that's O(n) per merge, O(n²) total; pass a shared accumulator instead.
Approach 2 of 2 · Optimal
Iterative Inorder with an Explicit Stack (+ Morris)
1Hint 1Explore hintHide hint
Recursion is just a stack the runtime manages for you. To remove recursion, manage that stack yourself — what would you push, and when?
2Hint 2Explore hintHide hint
Walk as far left as possible, pushing every node onto a stack. When you can't go left, the top of the stack is the next node to visit (its left subtree is exhausted).
3Hint 3Explore hintHide hint
After visiting a popped node, move to its right child and repeat the 'go all the way left' process. Loop until both the stack is empty and the current pointer is null.
A · Core idea
The recursive version hides a stack inside the language runtime. The iterative version makes that stack explicit so you control the memory and can run on trees deep enough to overflow the call stack.
The core invariant. Maintain a curr pointer and a stack. Repeatedly push curr and move to curr.left until curr is null — this stacks up an entire left spine. When you can go no further left, the node on top of the stack has no unvisited left subtree, so it's exactly the next inorder value: pop it, record it, then set curr to its right child and repeat. The loop ends only when both the stack is empty and curr is null.
Why this produces inorder specifically. A node is recorded only after its whole left subtree has been pushed and drained. Then we pivot to the right subtree. That's the literal definition of left-node-right. Preorder iterative is simpler (push right then left, visit on pop); postorder iterative usually needs two stacks or a 'last visited' marker — worth mentioning but not worth writing unless asked.
Morris traversal — the O(1) flex. Recursion and an explicit stack both cost O(h) space. Morris traversal achieves O(1) extra space by temporarily rewiring the tree: for each node with a left child, find that left subtree's rightmost node (the inorder predecessor) and point its null right pointer back to the current node, creating a temporary 'thread' that lets you climb back up without a stack. On the second visit you tear the thread down, restoring the tree. It's O(n) time still (each edge is traversed at most twice) and a genuine standout answer — but state the trade-off: it mutates the tree mid-traversal, so it's risky in concurrent or read-only settings.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,null,2,3]Interactive diagram
Picking the right traversal
curr=1All three DFS orders differ only by where the visit happens; BFS is a different animal for level grouping.
[1,3,2]C · Code with teaching comments
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
Any recursive traversal can be made iterative by simulating the call stack with an explicit Stack/list. The trick that makes interviewers nod is articulating the invariant out loud — 'a node is on the stack while its left subtree is still being processed' — rather than just reciting the loop.
ComplexityO(n) time, O(h) space — Every node is pushed and popped exactly once → O(n) time. The stack holds at most one full root-to-leaf path of nodes, so its size is bounded by the height h → O(h) space. Morris traversal drops this to O(1) by reusing null right-pointers as temporary threads.
E · Edge cases and pitfalls6root = [] — curr starts null and stack is empty, so the while condition is false immediately → returns [].Explore edge casesHide edge cases
Edge cases handled
root = []curr starts null and stack is empty, so the while condition is false immediately → returns [].root = [1] (single node)Push 1, inner loop ends, pop and visit 1, right is null → returns [1].Left-skewed tree [3,2,null,1]Stack fills to depth = height (O(n) here); nodes pop in order 1,2,3 — the iterative version still uses O(h) space, which degrades to O(n) on a degenerate tree.
Pitfalls
- Visiting a node when you push it instead of when you pop it — that yields preorder, not inorder.
- Forgetting to move to curr.right after the pop, causing an infinite loop or missed right subtrees.
- Reaching for Morris traversal in a concurrent or read-only context — it temporarily mutates the tree's pointers.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<Integer> inorderTraversal(TreeNode root) { List<Integer> out = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Wrong visit position (preorder when inorder asked)
The three orders share the same recursion skeleton, so a single misplaced line silently returns the wrong order. For [1,null,2,3], preorder gives [1,2,3] but inorder must give [1,3,2].
Explore the code comparisonHide the code comparison
Wrong visit position (preorder when inorder asked)
The three orders share the same recursion skeleton, so a single misplaced line silently returns the wrong order. For [1,null,2,3], preorder gives [1,2,3] but inorder must give [1,3,2].
Don't write this
def inorder(node):
if not node:
return
out.append(node.val) # visiting BEFORE left → this is PREorder
inorder(node.left)
inorder(node.right)Write this instead
def inorder(node):
if not node:
return
inorder(node.left)
out.append(node.val) # visit BETWEEN the two recursions → inorder
inorder(node.right)2Visiting on push in the iterative version
If you record the value when you push the node onto the stack, you emit it before its left subtree — that's preorder. Inorder requires recording only when you pop.
Explore the code comparisonHide the code comparison
Visiting on push in the iterative version
If you record the value when you push the node onto the stack, you emit it before its left subtree — that's preorder. Inorder requires recording only when you pop.
Don't write this
while (curr != null) {
out.add(curr.val); // recorded on the way DOWN → preorder
stack.push(curr);
curr = curr.left;
}Write this instead
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
out.add(curr.val); // recorded on the way UP → inorder3Concatenating subtree lists at every node
Returning a new list per node and concatenating (left + [val] + right) copies O(n) elements at upper levels, degrading to O(n²). Pass a single shared accumulator instead.
Explore the code comparisonHide the code comparison
Concatenating subtree lists at every node
Returning a new list per node and concatenating (left + [val] + right) copies O(n) elements at upper levels, degrading to O(n²). Pass a single shared accumulator instead.
Don't write this
def inorder(node):
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)Write this instead
out = []
def inorder(node):
if not node:
return
inorder(node.left)
out.append(node.val)
inorder(node.right)Revise
Carry the pattern into the interview
Pattern to remember
Depth-first tree walk (pre/in/post) + explicit-stack iterative variant
Code pattern to memorize
preorder: visit(node); dfs(left); dfs(right)
inorder: dfs(left); visit(node); dfs(right)
postorder: dfs(left); dfs(right); visit(node)Rules to remember
- 1The only difference between the three orders is where you place the
visit(node)line relative to the two recursive calls. - 2Inorder of a BST is sorted — this single fact powers Validate BST, Kth Smallest, and BST iterators.
- 3Always handle the
nullnode as the base case first, or you dereference a null child. - 4Iterative inorder: push lefts onto a stack, pop to visit, then dive right. Stack depth is
O(h), notO(n). - 5Recursion uses the call stack (
O(h)hidden space); the iterative version makes that stack explicit so you control it.
Use this pattern when
- You must process every node and the *order* of processing matters
- Inorder specifically when the tree is a BST and you want values in sorted order
- Preorder when you need to copy/serialize a tree top-down (root before children)
- Postorder when a node's result depends on its children (heights, deletes, bottom-up DP)
Choose another pattern when
- You need nodes grouped *by level* → that's BFS / level-order, not DFS
- You need the shortest path / minimum depth → BFS short-circuits earlier
- Order genuinely doesn't matter → any traversal works; pick the simplest
Interview takeaway
Traversal is the alphabet of tree problems. Memorize that the three DFS orders differ only by the position of the visit, that inorder on a BST yields sorted output, and that an explicit stack converts any recursion into iteration. Almost every tree question is one of these walks with a tiny bit of bookkeeping bolted on.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternDepth-first traversal is the foundational tree pattern. Recognise it whenever you must touch every node in a defined order. Postorder for bottom-up aggregation (heights, sums), preorder for top-down construction (copy, serialize), inorder for sorted BST output. The explicit-stack conversion and Morris traversal are the space-optimization layers on top.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Binary Tree Preorder TraversalComing soonSame template — move the visit before both recursive calls; iterative version pushes right child then left.
- Binary Tree Postorder TraversalComing soonVisit after both children; iterative trick is to do a reversed preorder (node,right,left) and reverse the output.
- Binary Tree Level Order TraversalSwitch from DFS to BFS — use a queue and process one level per outer-loop iteration.
- Kth Smallest Element in a BSTInorder on a BST is sorted — stop after popping the kth node in the iterative inorder.