DSA AnimatorDSA animations
Binary Tree Inorder Traversal LC #94 Easy Tree · Stack
Problem

Given the root of a binary tree, return the inorder traversal of its values: left subtree → node → right subtree. Follow-up: do it iteratively instead of recursively.

Example 1
Input: root = [1,null,2,3]
Output: [1,3,2]
Example 2
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Constraints: 0 ≤ nodes ≤ 100  |  −100 ≤ Node.val ≤ 100
🌳 Tree
Level order, like LeetCode: 1,null,2,3 · up to 15 nodes
📚 stack
curr waiting on stack visited ∅ null, so stop diving ⬇️ visited values drop straight down: left-to-right = inorder
Variables
curr
—
stack size
0
res
[]
💡 Step Logic
Press ▶ Play or Next to begin.
✓
Ready
0 / 0
Pick an example and press Play.
Algorithm
1
⬅️ While curr isn't null: push it 📚 and go left
2
∅ Hit null → pop the top and visit it ✅
3
➡️ Move to its right child and repeat until curr is null and the stack is empty
Time
O(n)
Space
O(h) stack
🧠 Why it works

Recursive inorder is go(left); visit(node); go(right). The stack stores exactly the nodes whose go(left) call is still running. Each node is pushed once and popped once, so the whole traversal is O(n). Bonus: on a BST, inorder gives the values in sorted order, which is behind "Validate BST" (98) and "Kth Smallest" (230).

⚠️ Edge cases & follow-ups

Empty tree → [] (the loop never runs). Left-skewed tree → stack grows to n, so worst-case space is O(n). Loop condition must be curr != null || !stack.isEmpty(): either one alone stops too early. Morris traversal gets O(1) extra space by temporarily threading right pointers.