#94 Binary Tree Inorder Traversal
the problem
In plain words
Return the values of a binary tree in inorder: everything in the left subtree, then the node itself, then everything in the right subtree. The recursive version is short — also write it without recursion.
in root = [1,null,2,3]
out [1,3,2]
1 has no left subtree, so it comes first; then 2's left subtree (3), then 2.
in root = [1,2,3,4,5,null,8,null,null,6,7,9]
out [4,2,6,5,7,1,3,9,8]
in root = []
out []
in root = [1]
out [1]
- 0 ≤ number of nodes ≤ 100
- -100 ≤ Node.val ≤ 100
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternIterative tree DFS (explicit stack)
Replace the call stack with your own: dive left pushing every node, pop one — nothing unvisited is left of it — visit it, then do the same for its right subtree.
solutions
From brute force to optimal
walk(left), add the node, walk(right).
- null → return.
- walk(node.left).
- out.add(node.val).
- walk(node.right).
Each node is entered once with O(1) work.
One stack frame per level of the current path — n frames on a skewed tree.
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> out = new ArrayList<>(); walk(root, out); return out; } private void walk(TreeNode node, List<Integer> out) { if (node == null) return; walk(node.left, out); // the whole left subtree first out.add(node.val); // then this node walk(node.right, out); // then the right subtree }}Push the left spine, pop one node, visit it, then move to its right child and repeat.
- cur = root.
- While cur != null or the stack isn't empty:
- push cur and go left until cur is null.
- cur = pop(); add cur.val; cur = cur.right.
Each node is pushed once and popped once.
The stack holds the left spine of the current path — on the heap, so no StackOverflowError.
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> out = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); // nodes we still have to come back to TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { // dive left, remembering the path stack.push(cur); cur = cur.left; } cur = stack.pop(); // nothing unvisited on its left out.add(cur.val); cur = cur.right; // then walk its right subtree } return out; }}Dry run
Before going left, point the rightmost node of the left subtree back at the current node (a thread). Coming back up that thread means the left side is done.
- No left child → visit, go right.
- Else find pred = rightmost node of the left subtree.
- pred.right == null → set it to cur (thread) and go left.
- pred.right == cur → remove the thread, visit cur, go right.
Each edge is walked a constant number of times: down once, and once more while finding a predecessor.
Two pointers. The threads reuse empty right links and are removed before the walk ends.
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> out = new ArrayList<>(); TreeNode cur = root; while (cur != null) { if (cur.left == null) { // nothing on the left: visit, go right out.add(cur.val); cur = cur.right; continue; } TreeNode pred = cur.left; // rightmost node of the left subtree while (pred.right != null && pred.right != cur) pred = pred.right; if (pred.right == null) { // first time here: leave a thread back to cur pred.right = cur; cur = cur.left; } else { // came back up the thread: left side is done pred.right = null; // remove the thread, restoring the tree out.add(cur.val); cur = cur.right; } } return out; }}in the room
How to say it in the interview
talk track
- Give the recursive version in one breath, then say: "the follow-up wants it iteratively, so I'll manage the stack myself."
- Explain the loop — dive left pushing, pop, visit, go right — and dry-run [1,null,2,3].
- State O(n) time, O(h) space; offer Morris for O(1) space if they push further.
traps
- Adding the value when you push the node — that's preorder. Inorder adds it when you pop.
- Looping on
!stack.isEmpty()alone: it exits before exploring the last popped node's right subtree. - Morris: forgetting to remove a thread leaves a cycle in the tree.
what they ask next
Follow-ups
Preorder iteratively (LC 144)?
Pop, visit, then push right before left so left comes out first.
Postorder iteratively (LC 145)?
Do root → right → left with a stack and reverse the output — or keep a prev pointer to know when you're coming back from the right child.
Binary Search Tree Iterator (LC 173)?
The same loop, paused: next() pops a node and pushes the left spine of its right child. O(h) memory, O(1) amortized per call.
before you submit
Edge cases to test
- Empty tree → [].
- Only left children: the output is the chain from the bottom up, and the stack grows to n.
- Only right children: the output is top-down and the stack never holds more than one node.
- Duplicate values are fine — the order comes from the structure, not the values.
practise next
Similar problems
- #230Kth Smallest Element in a BSTMediumin BST
- #173Binary Search Tree IteratorMediumin BST
- #102Binary Tree Level Order TraversalMediumin Traversals