Questions
6 of 26
How do you implement Inorder traversal iteratively? (Without recursion)
Difficulty: 3/10
Iterative Inorder Traversal
Iterative inorder traversal replaces the recursion call stack with an explicit stack. I repeatedly push every left node, process the top node when no further left child exists, and then move to its right subtree. This preserves the exact Left-Root-Right traversal order.
javascript
- 1
Time complexity: O(n).
- 2
Auxiliary space: O(h), where h is tree height.
- 3
The explicit stack simulates the recursive call stack.
- 4
For a BST, the resulting list is sorted.
Follow-up Questions
- How would you implement iterative preorder traversal?
- Can inorder traversal be implemented with O(1) auxiliary space?