Why it works
- A node goes on the stack on the way down and comes off only when everything left of it is done: the stack waits exactly like the calls of the recursive walk.
- After a node is added, cur moves to its right subtree, so the order is always left subtree, node, right subtree.
- Every node is pushed and popped once, so the loop ends when cur is none and nothing is waiting.
Complexity
Time O(n): every node is pushed and popped once. Memory O(h), where h is the height of the tree: the stack holds one path from the root down.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗