Iterative Preorder Traversal with a Stack

In our last lesson, we explored binary trees by traversing them "wide" using Breadth-First Search (BFS) and a queue. This level-by-level approach is powerful for finding the shortest path and for problems where you need to process nodes by depth. Now, we'll pivot to a different strategy: going "deep" with Depth-First Search (DFS).

DFS explores as far as possible down one branch before backtracking. There are three primary ways to do this, distinguished by the order in which they visit the root node relative to its subtrees: preorder, inorder, and postorder.

Today's lesson focuses on the first of these: iterative preorder traversal. You will learn how to implement the Root -> Left -> Right traversal sequence using an explicit stack. This mimics the behavior of the recursive call stack, giving you precise control and helping to avoid stack overflow on very deep trees. Mastering this pattern is fundamental for many other tree algorithms.

What is Preorder Traversal?

Preorder traversal follows a simple, consistent rule:

1. Visit the current node.
2. Traverse the entire left subtree.
3. Traverse the entire right subtree.

This "visit first" approach is useful for tasks like creating a copy of a tree or serializing it, as you process the root before its descendants. For a tree like [1, 2, 3, 4, 5], the traversal would be 1 -> 2 -> 4 -> 5 -> 3.

While recursion provides a very natural way to express this, the iterative approach using a stack is a core skill for interviews and for understanding how traversal works under the hood.

Method 1: The Intuitive "Pop-and-Visit" Approach

Let's start with the most direct way to implement iterative preorder traversal. This method leverages the Last-In, First-Out (LIFO) nature of a stack to achieve the correct order.

The algorithm is as follows:

1. If the root is null, return an empty list.
2. Create a stack and push the root node onto it.
3. While the stack is not empty:
   a. Pop a node from the stack. Let's call it current.
   b. Process current (e.g., add its value to your result list).
   c. Push the right child of current onto the stack (if it exists).
   d. Push the left child of current onto the stack (if it exists).

The most important step here is the order of pushing children. Why push the right child first, then the left? Because a stack is LIFO. By pushing the left child last, you ensure it's the first one to be popped and processed in the next iteration, perfectly matching the Root -> Left -> Right sequence.

The following image provides an excellent step-by-step visualization of this exact process. Pay close attention to how the stack's state changes with each pop and subsequent pushes.

To see this logic explained and coded, the following video provides a concise walkthrough.

Method 2: The Generalizable "Unified Template"

While the first method is very clean for preorder, there's another approach that is incredibly valuable because it creates a unified template that can be easily adapted for inorder and postorder traversals. As you enjoy finding reusable patterns, this one is worth mastering.

This method uses a currentNode pointer to simulate the recursive descent more closely.

The algorithm is:

1. Create an empty stack and a currentNode pointer initialized to root.
2. Loop as long as currentNode is not null OR the stack is not empty.
3. Inside the loop, have an inner while loop that runs as long as currentNode is not null:
   a. Visit currentNode (add its value to the result).
   b. Push currentNode onto the stack (to save it for backtracking).
   c. Move left: currentNode = currentNode.left.
4. When the inner loop finishes, currentNode is null. This means we've hit the bottom of a left path. To backtrack, pop a node from the stack and set currentNode to its right child to begin exploring the right subtree.

This structure mirrors recursion: the outer loop keeps the process going, the inner while loop dives down the left side, and the pop-and-move-right step acts as the backtrack.

The following resource provides a fantastic explanation of both methods and compares them, highlighting the power of this unified template.

For a coding walkthrough of a similar cur-pointer-based approach, NeetCodeIO offers a clear implementation.

Complexity Analysis

For both iterative methods, the complexity is the same and is crucial to know for interviews.

• Time Complexity: $O(N)$, where $N$ is the number of nodes. Each node is pushed onto the stack and popped from the stack exactly once.
• Space Complexity: $O(H)$, where $H$ is the height of the tree. This space is used by the explicit stack. In a worst-case scenario (a completely skewed tree, resembling a linked list), the height is $N$, making the space complexity $O(N)$. For a perfectly balanced tree, the height is $\log N$, leading to $O(\log N)$ space.

Conclusion

In this lesson, we dove into the world of iterative DFS with preorder traversal. You now have two distinct patterns in your toolkit for solving this problem.

Key Takeaways:

• Preorder traversal follows the order: Root -> Left -> Right.
• The intuitive iterative method involves popping a node, visiting it, then pushing its right child followed by its left child onto a stack.
• The "unified template" method uses a currentNode pointer to traverse down the left path while stacking nodes, then backtracks by popping and moving to the right subtree.
• The unified template is slightly more complex for preorder alone but is highly valuable as it can be easily adapted for inorder and postorder traversals.

In our next lesson, we will put this to the test. We'll tackle iterative inorder traversal, and you will see how a simple change to the "visit" step in our unified template is all that's needed to produce a completely different traversal order.