Iterative Inorder Traversal with a Stack

Welcome back! In our previous lesson, we established a powerful "unified template" for iterative Depth-First Search using a stack and a currentNode pointer, applying it to preorder traversal. The real value of that template lies in its adaptability.

Today, we'll modify that same pattern to implement iterative inorder traversal. Your goal is to master the Left -> Root -> Right traversal sequence using an explicit stack. You will see how a subtle but critical change in the timing of our "visit" step allows us to generate a completely different, and often very useful, node ordering. This is a fundamental pattern for many tree problems, especially those involving Binary Search Trees.

From Preorder to Inorder: A Shift in Timing

Let's quickly recall the three steps of a traversal: processing the current node (the "visit"), traversing the left subtree, and traversing the right subtree.

• Preorder (Root -> Left -> Right): We visit the node before beginning the traversal of its subtrees.
• Inorder (Left -> Root -> Right): We traverse the entire left subtree first, then visit the node, and finally traverse the entire right subtree.

The key to adapting our iterative template is to change when we add a node's value to our result list. In the preorder template, we visited the node right before pushing it onto the stack. For inorder, we will delay the visit until after we have exhausted a path to the left and are popping the node back off the stack.

The Algorithm: Iterative Inorder Traversal

The algorithm leverages the same general structure we saw last time, but with the "visit" step repositioned.

1. Initialize an empty stack, an empty result list, and a currentNode pointer set to the root.
2. Begin a loop that continues as long as currentNode is not null OR the stack is not empty. This condition ensures we process every node.
3. Go as far left as possible: Inside the loop, run an inner while loop as long as currentNode is not null.
   • Push the currentNode onto the stack. This saves the node so we can come back to it later.
   • Update currentNode to its left child: currentNode = currentNode.left.
4. Visit and go right: Once the inner loop terminates, currentNode is null. This signifies we've hit the end of a left branch. Now we backtrack.
   • Pop the most recent node from the stack and assign it to currentNode: currentNode = stack.pop().
   • Visit the popped node: Add its value to the result list. This is the "inorder" moment—we only process a node after its entire left subtree has been considered.
   • Move to the right subtree to begin exploring it: currentNode = currentNode.right. The main loop will then take this new currentNode and repeat the process, either diving down its left side or, if it's null, continuing to pop from the stack.

The following image captures a moment during this process. The traversal has moved down the left side of the tree, pushing nodes 1, 2, and 4 onto the stack. The next step would be to pop 4, visit it, and check its right child.

To see a detailed walkthrough and implementation, the following article from 'takeuforward' is an excellent resource. It uses the exact logic we've just described.

Visualizing the Simulation

For a dynamic explanation, nothing beats a video walkthrough. NeetCode provides a fantastic simulation that first explains how the recursive call stack works and then demonstrates how our iterative approach with an explicit stack perfectly mimics that behavior.

If you prefer a C++ or Java perspective, the take U forward channel also has a great dry run.

Complexity Analysis

Just as with preorder traversal, the complexity remains the same.

• Time Complexity: $O(N)$, where $N$ is the number of nodes in the tree. Every node is pushed onto and popped from the stack exactly once.
• Space Complexity: $O(H)$, where $H$ is the height of the tree. This is the maximum number of nodes that will be stored on the stack at any one time. In the worst case of a skewed tree (like a linked list), the height is $N$, making the space complexity $O(N)$. For a balanced tree, it is $O(\log N)$.

Conclusion

In this lesson, you've adapted the unified DFS template to perform iterative inorder traversal. By shifting the "visit" operation from before the push to after the pop, you've successfully changed the traversal order from Root -> Left -> Right to Left -> Root -> Right.

Key Takeaways:

• Inorder traversal visits nodes in the sequence: Left Subtree -> Root -> Right Subtree.
• The iterative algorithm involves a main loop that first pushes all nodes along a left-side path onto a stack.
• Nodes are only visited when they are popped from the stack, after which the algorithm proceeds to the node's right child.
• This pattern is a minor but powerful modification of the general iterative DFS template you learned previously.

We have now covered preorder and inorder traversals. The final variant, postorder traversal (Left -> Right -> Root), presents a more interesting challenge. In our next lesson, you'll see how to adapt our template once more to handle this case, which requires a clever trick to get the ordering right.