Iterative Preorder traversal of a Binary Tree in Java

1. Introduction

PreOrder traversal is a type of Depth-First Search (DFS) for binary trees. The visiting order is:

Root → Left Subtree → Right Subtree

This means for each node:

Visit the node itself.
Traverse the left subtree.
Traverse the right subtree.

2. Why Use Iterative Instead of Recursive?

Recursive traversal is elegant, but it:

Relies on the system’s call stack
May lead to StackOverflowError in deep trees
Doesn’t give control over the traversal flow

The iterative approach simulates recursion using an explicit stack and is preferred when:

Working with large or unbalanced trees
Avoiding recursion limits
Needing more control over the algorithm

3. PreOrder Traversal Pattern

In PreOrder traversal, you:

Visit the current node first
Then push the right child
Then push the left child

This ensures that the left subtree is processed before the right subtree (because stack is LIFO).

4. Step-by-Step Logic of Iterative PreOrder Traversal

Algorithm:

Create an empty stack.
Push the root node to the stack.
While the stack is not empty:
- Pop the node on top of the stack.
- Visit (print) the node’s data.
- Push right child to the stack if it exists.
- Push left child to the stack if it exists.

Why push right before left?

Because the stack is LIFO, pushing right first ensures that the left child is processed before the right child.

5. Java Implementation

import java.util.Stack;

class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int value) {
        data = value;
        left = right = null;
    }
}

public class IterativePreOrderTraversal {

    TreeNode root;

    // Iterative PreOrder Traversal
    public void preOrderIterative(TreeNode root) {
        if (root == null)
            return;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            System.out.print(current.data + " ");

            // Push right first so left is processed first
            if (current.right != null)
                stack.push(current.right);
            if (current.left != null)
                stack.push(current.left);
        }
    }

    public static void main(String[] args) {
        IterativePreOrderTraversal tree = new IterativePreOrderTraversal();

        // Constructing the binary tree:
        /*
                1
              /   \
             2     3
            / \   / 
           4   5 6   
        */
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        tree.root.right.left = new TreeNode(6);

        System.out.println("Iterative PreOrder Traversal:");
        tree.preOrderIterative(tree.root);  // Output: 1 2 4 5 3 6
    }
}

Learnitweb