Introduction

Depth-First Search (DFS) is a fundamental algorithm for traversing or searching tree structures. While recursive implementations are often elegant and concise, they can lead to stack overflow errors with very deep trees. An iterative approach using an explicit stack is a robust alternative. This article demonstrates how to implement the three primary DFS traversals—pre-order, in-order, and post-order—for binary trees without recursion.

Binary Tree Traversal Types

For any given binary tree node, there are three distinct ways to visit it and its children. The difference between the traversal types lies in the order of these visits:

• Pre-order Traversal: Visit the root node first, then recursively traverse the left subtreee, and finally the right subtree. The order is: Root, Left, Right.
• In-order Traversal: Recursively traverse the left subtree first, visit the root node, and then recursively traverse the right subtree. The order is: Left, Root, Right.
• Post-order Traversal: Recursively traverse the left subtree, then the right subtree, and visit the root node last. The order is: Left, Right, Root.

Recursive Implementations

Before diving into the iterative solutions, let's quickly review the recursive versions, as they establish the core logic for each traversal type.

Pre-order Traversal (Recursive)

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.data = val;
    }
}

void traversePreOrderRecursive(TreeNode root) {
    if (root == null) {
        return;
    }
    visit(root); // Process the current node
    traversePreOrderRecursive(root.left);
    traversePreOrderRecursive(root.right);
}

In-order Traversal (Recursive)

void traverseInOrderRecursive(TreeNode root) {
    if (root == null) {
        return;
    }
    traverseInOrderRecursive(root.left);
    visit(root); // Process the current node
    traverseInOrderRecursive(root.right);
}

Post-order Traversal (Recursive)

void traversePostOrderRecursive(TreeNode root) {
    if (root == null) {
        return;
    }
    traversePostOrderRecursive(root.left);
    traversePostOrderRecursive(root.right);
    visit(root); // Process the current node
}

Iterative (Non-Recursive) Implementations

The iterative approach relies on an explicit stack to simulate the call stack used in recursion. We manually manage the nodes to be visited.

Pre-order Traversal (Iterative)

The logic is to push the root onto the stack, then enter a loop. In each iteration, pop a node, visit it, and then push its right child followed by its left child onto the stack. This ensures that the left child is processed before the right child.

void traversePreOrderIterative(TreeNode root) {
    if (root == null) {
        return;
    }

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

    while (!stack.isEmpty()) {
        TreeNode current = stack.pop();
        visit(current);

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

In-order Traversal (Iterative)

The logic is to traverse to the leftmost node, pushing all nodes along the path onto the stack. Once the leftmost node is reached, pop and visit it. Then, move to its right subtree and repeat the process.

void traverseInOrderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        // Reach the leftmost node of the current subtree
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        // Current must be null at this point
        current = stack.pop();
        visit(current); // Visit the node

        // Now, visit the right subtree
        current = current.right;
    }
}

Post-order Traversal (Iterative)

This is the most complex of the three. A common strategy is to use a single stack and a pointer to the last visited node. This helps determine if we are moving up from the left or right subtree. If we are moving up from the left, we need to process the right subtree before visiting the node. If we are moving up from the right, we can safely visit the node.

void traversePostOrderIterative(TreeNode root) {
    if (root == null) {
        return;
    }

    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    TreeNode lastVisited = null;

    while (current != null || !stack.isEmpty()) {
        // Traverse to the leftmost node
        if (current != null) {
            stack.push(current);
            current = current.left;
        } else {
            TreeNode peekNode = stack.peek();
            // If the right child exists and hasn't been visited yet
            if (peekNode.right != null && lastVisited != peekNode.right) {
                current = peekNode.right;
            } else {
                visit(peekNode);
                lastVisited = stack.pop();
            }
        }
    }
}