#94
Binary Tree Inorder Traversal
Easy Iterative inorder with a stack
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the values of a binary tree in inorder (left subtree, node, right subtree).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: list nodes as left subtree, node, right subtree.
Why this works: the iterative version pushes all left children, pops one, visits it, then moves to its right child.
Example: 1 with right child 2, and 2 has left child 3
go left from 1: none → visit 1go to 2 → left 3 → visit 3, visit 2[1, 3, 2]
✦Hints open one at a time
The recursive version is three lines. Try the iterative one too.
Go left as far as possible, pushing nodes. Pop one, visit it, then go to its right child.
↗Approach
cur = root. While cur or the stack is non-empty: push all left children, pop the top, record it, set cur to its right child.
</>Solution (Java)
import java.util.*;
/**
* Definition for a binary tree node (provided by LeetCode):
* class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> st = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !st.isEmpty()) {
while (cur != null) { // go all the way left
st.push(cur);
cur = cur.left;
}
cur = st.pop();
res.add(cur.val); // visit between left and right
cur = cur.right;
}
return res;
}
}!Common mistake
Visiting the node when it's pushed — that's preorder, not inorder.
Complexity
- Time: O(n).
- Space: O(h), h = tree height.
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon