Iterative inorder traversal
Do the same left-root-right walk with your own stack instead of the recursive call stack. About 12 minutes.
What recursion was doing for you
Every recursive call to inorder_traversal(root.left) sits on the call stack, waiting, until that call returns. That waiting call is exactly how the program remembers "come back to this node once its left subtree is done." An iterative version has to build that same memory itself, with its own stack of nodes.
- stack
- [5, 3, 1]
- result
- []
Walk left as far as you can, pushing every node you pass: 5, 3, 1.
Go left, pop, go right
Walk left as far as possible, pushing every node you pass. When you can't go left anymore, pop the top of the stack — that node's entire left subtree has just been visited, so visit it now, then move to its right child and repeat the whole process from there. Stop once current is null and the stack is empty.
In the iterative version, when a node is popped off the stack, what does that tell you?
- AThat node's whole left subtree has already been visited
- BThat node's whole right subtree has already been visited
- CNothing — the stack order doesn't mean anything here
Show the answer
That node's whole left subtree has already been visited. You only pushed the node while walking left, so popping it back means nothing to its left is left to visit.
Iterative inorder traversal
Given the root of a binary tree, return the values of its nodes in inorder (left subtree, then the current node, then right subtree) — but without recursion. Use your own stack to keep track of the nodes you still need to come back to. If the tree is empty, return an empty list.
root = [5, 3, 8] → [3, 5, 8]
0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val ≤ 1,000,000