Binary Tree Inorder Traversal
Problem
root of a binary tree, return the node values in
in-order: for every node, first everything in its left subtree, then the node
itself, then everything in its right subtree. An empty tree gives an empty list.root = [1,null,2,3]Output[1,3,2]root = [4,2,6,1,3]Output[1,2,3,4,6]root = []Output[]0 ≤ n ≤ 100 · -100 ≤ Node.val ≤ 100 · Follow-up: recursion is trivial — can you do it iteratively?
Try it yourself
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
}
}
Instinct The tree is a BST? Its in-order walk is a sorted list and every node splits the search space - think "sorted array in tree form", not "visit everything".
Memory hack Left is less, right is more, in-order reads the sorted score - and every node lives inside a (low, high) fence set by its ancestors.
Open the Binary Search Tree & In-order guide →Approaches
Brute ForceRecursive DFS
O(n)Space O(h)Direct translation of the definition: recurse left, add the node, recurse
right. Each node is visited once; the call stack holds one frame per level, so space
is the height h (n for a skewed tree, log n if balanced).
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); dfs(root, res); return res; } private void dfs(TreeNode node, List<Integer> res) { if (node == null) return; dfs(node.left, res); res.add(node.val); dfs(node.right, res); }
Three lines and obviously correct, but depth is limited by the call stack.
BetterIterative with Explicit Stack
O(n)Space O(h)Simulate the call stack. Push the whole left spine of curr; when you
hit null, pop the top — its left side is done — record it, and continue
from its right child. Each node is pushed and popped exactly once.
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { // dive down the left spine stack.push(curr); curr = curr.left; } curr = stack.pop(); // leftmost unvisited node res.add(curr.val); curr = curr.right; } return res; }
Same cost, no recursion-depth risk; the template behind BST iterators.
OptimalMorris Traversal (Threaded Tree)
O(n)Space O(1)Before going left, link the in-order predecessor (rightmost node of the left
subtree) back to curr. That thread is our way home. Finding the thread a
second time means the left side is finished: remove it, emit curr, go
right. Each edge is walked at most a constant number of times, so total work is O(n).
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); TreeNode curr = root; while (curr != null) { if (curr.left == null) { res.add(curr.val); curr = curr.right; } else { TreeNode pred = curr.left; while (pred.right != null && pred.right != curr) pred = pred.right; if (pred.right == null) { // first visit: create thread, go left pred.right = curr; curr = curr.left; } else { // second visit: remove thread, emit pred.right = null; res.add(curr.val); curr = curr.right; } } } return res; }
Constant extra memory; temporarily mutates the tree but restores it fully.
res.add(curr.val) into the “create thread” branch and
you get Morris pre-order for free.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Recursive DFS | O(n) | O(h) |
| Better | Iterative with Explicit Stack | O(n) | O(h) |
| Optimal | Morris Traversal (Threaded Tree) | O(n) | O(1) |
- Loop condition
while (!stack.isEmpty())alone — exits before the root is pushed. - Morris: forgetting
pred.right = nullleaves cycles in the caller's tree. - Morris predecessor loop without
pred.right != curr— spins forever on a thread.
- Give recursion first, then offer the stack version as the follow-up answer.
- Mention Morris for O(1) space, and that it mutates the tree during the walk.
- Note that on a BST, in-order yields values in sorted order.