L9: Iterative Preorder Traversal in Binary Tree

This chapter explores how to perform an Iterative Preorder Traversal on a Binary Tree. While recursive traversals rely implicitly on the system call stack, the iterative approach uses an explicit data structure—the Stack—to manage node traversal without risking stack overflow on deeply skewed trees.

1. Why Do We Need Iterative Preorder Traversal?

• Recursion Limitations: Recursive tree traversals utilize the underlying call stack. In extremely deep or skewed trees (e.g., a tree where every node has only a right child), this can lead to a StackOverflowError.
• Explicit Control: Managing traversal via an explicit data structure gives developers absolute control over memory and execution flow.
• Interview Relevance: Iterative tree traversals are fundamental algorithmic interview questions that test a developer's understanding of data structures (specifically LIFO stacks) and tree properties.

2. Core Mental Model: The Stack and LIFO

• Preorder Traversal Rule: Root -> Left -> Right.
• The Stack Property: A Stack is a LIFO (Last-In, First-Out) data structure.
• The Catch: Because a stack pops the most recently added item first, if we want to process the Left child before the Right child, we must push the Right child onto the stack before pushing the Left child.

Stack Push Order for Preorder:
1. Push Right Child (Processed later because it's at the bottom)
2. Push Left Child  (Processed first because it's at the top)

3. Naive vs. Intuitive Manual Walkthrough

Let's consider a sample binary tree to understand the mechanics of preorder traversal:

• Root: 1
• Left Subtree: 2 (with children 3 and 4)
• Right Subtree: 5 (with children 6 and 7)

Recursive Order Recap:

1. Visit and print Root (1).
2. Traverse Left subtree recursively (2 -> 3, 4).
3. Traverse Right subtree recursively (5 -> 6, 7).

• Expected Preorder Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

4. Step-by-Step Iterative Algorithm Evolution

To implement this iteratively, we simulate the recursion stack using an explicit Stack data structure.

Algorithm Steps:

1. Check for Edge Cases: If the root is null, return an empty list or terminate.
2. Initialize Stack: Create a Stack and push the root node into it.
3. Loop Until Stack is Empty:
   • Pop the top element from the stack (current).
   • Print or store the value of current (this satisfies the Root requirement).
   • Push the Right child of current onto the stack (if it exists).
   • Push the Left child of current onto the stack (if it exists).
4. Repeat until the stack contains no more nodes.

5. Complete Flow Walkthrough

Let's trace the algorithm on our tree: Root = 1, Left child = 2, Right child = 5.

Initial State:
Stack: [ 1 ]
Output: [ ]

Step 1:
- Pop `1`. Print `1`.
- Push Right (`5`), then push Left (`2`).
Stack: [ 5, 2 ]  (Top is 2)
Output: [ 1 ]

Step 2:
- Pop `2`. Print `2`.
- Push Right of 2, then Left of 2 (let's assume children 3 and 4).
Stack: [ 5, 4, 3 ] (Top is 3)
Output: [ 1, 2 ]

Step 3:
- Pop `3`. Print `3`. (Assume no children)
Stack: [ 5, 4 ] (Top is 4)
Output: [ 1, 2, 3 ]

Step 4:
- Pop `4`. Print `4`.
Stack: [ 5 ] (Top is 5)
Output: [ 1, 2, 3, 4 ]

Step 5:
- Pop `5`. Print `5`.
- Push Right and Left children of 5 (`6` and `7`).
Stack: [ 7, 6 ] (Top is 6)
Output: [ 1, 2, 3, 4, 5 ]

The process continues until all nodes are popped and printed in correct Preorder sequence.

6. Implementation Code (C++ & Java)

C++ Implementation

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

vector<int> preorderTraversal(Node* root) {
    vector<int> preorder;
    if (root == nullptr) {
        return preorder;
    }
    
    stack<Node*> st;
    st.push(root);
    
    while (!st.empty()) {
        Node* currNode = st.top();
        st.pop();
        
        // Visit the root
        preorder.push_back(currNode->data);
        
        // Push right first so that left is processed first (LIFO property)
        if (currNode->right != nullptr) {
            st.push(currNode->right);
        }
        if (currNode->left != nullptr) {
            st.push(currNode->left);
        }
    }
    
    return preorder;
}

Java Implementation

import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> preorder = new ArrayList<>();
        if (root == null) {
            return preorder;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode currNode = stack.pop();
            
            // Visit the root
            preorder.add(currNode.val);
            
            // Push right child first, then left child
            if (currNode.right != null) {
                stack.push(currNode.right);
            }
            if (currNode.left != null) {
                stack.push(currNode.left);
            }
        }
        
        return preorder;
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Preorder Sequence: Follows the traversal order of Root -> Left -> Right.
• Explicit Stack Usage: Eliminates recursion overhead and prevents system stack overflow errors on skewed trees.
• Push Order Matters: Because stacks are LIFO, you must push the Right child before the Left child so that the Left child is popped and processed first.
• Time Efficiency: Operates in linear time $O(N)$ as each node is visited once.
• Space Efficiency: Requires $O(N)$ auxiliary space in the worst-case (skewed trees) for the stack storage.