Why it works
- A node is added the moment it comes off the stack, before any node under it has even been popped.
- The stack gives back the last thing put on it, so pushing right before left makes the whole left subtree come out before the right child.
- Every node is pushed once, the root at the start and the rest by their parent, and popped once, so the loop ends after n pops.
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 the right children waiting along one path.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗