How do you implement Inorder traversal iteratively? (Without recursion)

Difficulty: 3/10

binary tree, stack, iteration

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.

Scenario Questions

0-2 years experience

2-5 years experience

1Your team added a feature that prints node values during an inorder traversal, but the output order is wrong after a recent refactor. Walk me through how you'd debug the iterative implementation.

Follow-up Questions