Algorithms - 14. Iterative DFS (Tree Traversal with Stack)

When to use Iterative DFS

Use Iterative DFS when you need to traverse trees or graphs without recursion. While most commonly used for avoiding stack overflow on deep trees, it can be adapted for:

Binary tree traversals (in-order, pre-order, post-order) - classic use case
Graph exploration when recursion depth might exceed limits
State space search with explicit control over the search path
Backtracking problems where you need fine-grained control over the stack
Tree serialization/deserialization with controlled memory usage
Finding paths in trees/graphs while maintaining the exact path
Any traversal where you need to pause, resume, or inspect the call stack

Example problem

Expression Tree Evaluation: Given a binary tree representing the expression ((3 + 5) * 2) - 7:

Traverse the tree to:

Print the expression in different notations (prefix, infix, postfix)
Evaluate the expression value
Find all leaf nodes (operands)

After processing:

Pre-order (prefix): - * + 3 5 2 7 (Polish notation)
In-order (infix): 3 + 5 * 2 - 7 (standard notation, needs parentheses)
Post-order (postfix): 3 5 + 2 * 7 - (Reverse Polish notation)
Result: 9
Leaf nodes: 7

Answer: Different traversal orders give us different expression notations, and iterative DFS lets us control exactly when and how we process each node.

What Iterative DFS Actually Does

Iterative DFS simulates the recursive call stack explicitly using a data structure (usually a stack). Instead of relying on the system's call stack for recursion, we manually manage our own stack to control the traversal order.

Think of it like navigating a multi-story building:

Recursive DFS: Taking an elevator that automatically stops at each floor
Iterative DFS: Taking the stairs where you control each step

How the Stack Operations Work

The Core Pattern - "Manually managing the call stack"

When traversing with a stack:

Push nodes onto the stack (like making a recursive call)
Pop nodes from the stack (like returning from a recursive call)
Process nodes at the right moment (depends on traversal order)
Track state if needed (for complex traversals like post-order)

The Three Classic Tree Traversals

In-order Traversal - "Left, Root, Right"

Process pattern:

Go as far left as possible (pushing nodes onto stack)
When can't go left, process current node
Then explore right subtree
Repeat until stack is empty

Pre-order Traversal - "Root, Left, Right"

Process pattern:

Process node immediately when visiting
Push right child for later (if exists)
Move to left child
When no left child, pop from stack

Post-order Traversal - "Left, Right, Root"

Process pattern:

Track whether we've visited children
First visit: push children onto stack
Second visit: process the node
Most complex of the three patterns

When These Patterns Apply

These patterns map directly to many real-world scenarios:

// Pre-order: Process parent before children (top-down)
// Example: Copying a tree, serializing structure

// In-order: Process in sorted order (for BST)
// Example: Getting sorted values, range queries

// Post-order: Process children before parent (bottom-up)
// Example: Calculating sizes, deleting nodes, evaluating expressions

The beauty of iterative DFS is that you have complete control over the traversal - you can pause, inspect the stack, or modify the traversal strategy mid-execution!

Single most important insight

Replace recursive calls with explicit stack operations, where pushing simulates calling and popping simulates returning - and by carefully controlling when we process nodes relative to stack operations, we can achieve any traversal order without recursion.

Mental note: The algorithm's genius lies in recognizing that recursion is just automatic stack management. By making the stack explicit, we gain complete control over the traversal. At each step, we decide: "What would the recursive version do here?" and translate that into push/pop operations.

Decision Framework

Each traversal involves different decisions about when to process and what to push:

In-order Decision Points:

Can go left? Push current and go left
Can't go left? Process current and go right
Track "current" pointer separate from stack

Pre-order Decision Points:

Process immediately upon visiting
Save right for later (push to stack)
Continue with left

Post-order Decision Points:

First visit? Mark as unvisited and push children
Second visit? Process the node
Need extra state to track visits

Code

// Definition for a binary tree node
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// === IN-ORDER TRAVERSAL (Left, Root, Right) ===
// Visit pattern: Go left → Process node → Go right
function inorderTraversal(root) {
  const collectedValues = [];
  const nodesToProcess = [];
  let currentPosition = root;

  // Continue while we have nodes to explore
  const hasMoreNodesToProcess = () => {
    return currentPosition != null || nodesToProcess.length > 0;
  };

  while (hasMoreNodesToProcess()) {
    // DECISION FRAMEWORK: Can we go deeper left?
    const canGoLeft = currentPosition != null;

    if (canGoLeft) {
      // Phase 1: Go as far left as possible
      // Save current node for later processing
      nodesToProcess.push(currentPosition);

      // Move to left child
      const leftChild = currentPosition.left;
      currentPosition = leftChild;
    } else {
      // Phase 2: Can't go left, time to process
      // Retrieve the next node to process
      const nodeToProcess = nodesToProcess.pop();
      currentPosition = nodeToProcess;

      // Process the node value (in-order position)
      const nodeValue = currentPosition.val;
      collectedValues.push(nodeValue);

      // DECISION FRAMEWORK: Now explore right subtree
      const rightChild = currentPosition.right;
      currentPosition = rightChild;
    }
  }

  return collectedValues;
}

// === PRE-ORDER TRAVERSAL (Root, Left, Right) ===
// Visit pattern: Process node → Go left → Go right
function preorderTraversal(root) {
  const collectedValues = [];
  const savedForLater = [];
  let currentPosition = root;

  // Continue while we have nodes to explore
  const hasMoreNodesToProcess = () => {
    return currentPosition != null || savedForLater.length > 0;
  };

  while (hasMoreNodesToProcess()) {
    // DECISION FRAMEWORK: Is there a node to process?
    const hasCurrentNode = currentPosition != null;

    if (hasCurrentNode) {
      // Phase 1: Process current node immediately
      const currentValue = currentPosition.val;
      collectedValues.push(currentValue);

      // DECISION FRAMEWORK: Save right child for later exploration
      const rightChild = currentPosition.right;
      const hasRightChild = rightChild != null;

      if (hasRightChild) {
        savedForLater.push(rightChild);
      }

      // Phase 2: Continue with left child
      const leftChild = currentPosition.left;
      currentPosition = leftChild;
    } else {
      // Phase 3: No left path, retrieve saved node
      const nextNode = savedForLater.pop();
      currentPosition = nextNode;
    }
  }

  return collectedValues;
}

// === POST-ORDER TRAVERSAL (Left, Right, Root) ===
// Visit pattern: Go left → Go right → Process node
function postorderTraversal(root) {
  const collectedValues = [];

  // Two parallel stacks to track nodes and their visit status
  const nodeStack = [root];
  const visitStatusStack = [false];

  // Continue while we have nodes in our stack
  const hasMoreNodesToProcess = () => {
    return nodeStack.length > 0;
  };

  while (hasMoreNodesToProcess()) {
    // Retrieve node and its visit status
    const currentNode = nodeStack.pop();
    const hasVisitedChildren = visitStatusStack.pop();

    // Skip null nodes
    const isValidNode = currentNode != null;

    if (isValidNode) {
      // DECISION FRAMEWORK: Have we already visited this node's children?
      if (hasVisitedChildren) {
        // Phase 2: Children processed, now process this node
        const nodeValue = currentNode.val;
        collectedValues.push(nodeValue);
      } else {
        // Phase 1: First visit - schedule node and children

        // Schedule current node for second visit (with visited=true)
        nodeStack.push(currentNode);
        visitStatusStack.push(true);

        // Schedule right child (will be processed second)
        const rightChild = currentNode.right;
        nodeStack.push(rightChild);
        visitStatusStack.push(false);

        // Schedule left child (will be processed first)
        const leftChild = currentNode.left;
        nodeStack.push(leftChild);
        visitStatusStack.push(false);
      }
    }
  }

  return collectedValues;
}

// === EXAMPLE USAGE: Expression Tree ===
// Build the expression tree: ((3 + 5) * 2) - 7
const expressionTree = new TreeNode(
  "-",
  new TreeNode(
    "*",
    new TreeNode("+", new TreeNode(3), new TreeNode(5)),
    new TreeNode(2)
  ),
  new TreeNode(7)
);

console.log("Expression Tree Traversals:");

// Pre-order gives prefix notation
const prefix = preorderTraversal(expressionTree);
console.log(`Pre-order (prefix): ${prefix.join(" ")}`);
// Output: - * + 3 5 2 7

// In-order gives infix notation (needs parentheses for correctness)
const infix = inorderTraversal(expressionTree);
console.log(`In-order (infix): ${infix.join(" ")}`);
// Output: 3 + 5 * 2 - 7

// Post-order gives postfix notation (RPN)
const postfix = postorderTraversal(expressionTree);
console.log(`Post-order (postfix): ${postfix.join(" ")}`);
// Output: 3 5 + 2 * 7 -

// === BONUS: Evaluate Expression Tree using Post-order ===
// Post-order ensures operands are evaluated before operators
function evaluateExpression(root) {
  // Two stacks for traversal control
  const nodeStack = [root];
  const visitStatusStack = [false];

  // Stack to accumulate calculated values
  const calculationStack = [];

  while (nodeStack.length > 0) {
    // Get current node and its visit status
    const currentNode = nodeStack.pop();
    const hasVisitedChildren = visitStatusStack.pop();

    const isValidNode = currentNode != null;

    if (isValidNode) {
      // DECISION FRAMEWORK: Process node or schedule children?
      if (hasVisitedChildren) {
        // Phase 2: Children processed, evaluate this node

        // Check if this is a leaf (operand) or internal node (operator)
        const isLeafNode =
          currentNode.left == null && currentNode.right == null;

        if (isLeafNode) {
          // Operand: push the number directly
          const operandValue = currentNode.val;
          calculationStack.push(operandValue);
        } else {
          // Operator: pop two operands and calculate
          const rightOperand = calculationStack.pop();
          const leftOperand = calculationStack.pop();
          const operator = currentNode.val;

          // Apply the operator
          let calculationResult;
          switch (operator) {
            case "+":
              calculationResult = leftOperand + rightOperand;
              break;
            case "-":
              calculationResult = leftOperand - rightOperand;
              break;
            case "*":
              calculationResult = leftOperand * rightOperand;
              break;
            case "/":
              calculationResult = leftOperand / rightOperand;
              break;
          }

          // Push result back for parent operations
          calculationStack.push(calculationResult);
        }
      } else {
        // Phase 1: First visit - schedule traversal

        // Re-schedule current node (mark as visited)
        nodeStack.push(currentNode);
        visitStatusStack.push(true);

        // Schedule right child
        const rightChild = currentNode.right;
        if (rightChild != null) {
          nodeStack.push(rightChild);
          visitStatusStack.push(false);
        }

        // Schedule left child
        const leftChild = currentNode.left;
        if (leftChild != null) {
          nodeStack.push(leftChild);
          visitStatusStack.push(false);
        }
      }
    }
  }

  // Final result is the only remaining value
  const finalResult = calculationStack[0];
  return finalResult;
}

const expressionResult = evaluateExpression(expressionTree);
console.log(`\nExpression result: ${expressionResult}`); // Output: 9

Doubt buster

Common doubt: "Why is post-order traversal so much more complex than in-order and pre-order? Can't we just rearrange when we process the node like we do for the other traversals?"

Why this seems like it should be simple

Looking at in-order and pre-order, the only difference is when we process the node:

// Pre-order: Process BEFORE going left
result.push(node.val);
// ... then go left

// In-order: Process BETWEEN left and right
// ... go left first
result.push(node.val);
// ... then go right

It seems like post-order should just be "process AFTER going right," but that doesn't work with a simple current pointer approach.

The key problem: Knowing when children are done

The fundamental issue is that post-order requires processing a node only after BOTH children have been fully processed.

Consider this tree:

    A
   / \
  B   C

For post-order (B, C, A), when we're at node A:

We need to process B's entire subtree first
Then process C's entire subtree
Only then can we process A

But here's the catch: When we pop A from the stack, how do we know if we've processed its children yet?

First time we see A: We shouldn't process it, we should explore children
Second time we see A: Now we can process it (children are done)

Why we need the "visited" flag

The visited flag solves this by tracking our traversal state:

// First encounter with node A
if (!visited) {
  // Don't process yet!
  // Push A back with visited=true
  // Push children with visited=false
}

// Second encounter with node A
if (visited) {
  // NOW we can process A
  // We know children have been handled
}

Alternative approach: Two stacks

Some people find this two-stack approach more intuitive:

function postorderTwoStacks(root) {
  if (root == null) return [];

  const stack1 = [root];
  const stack2 = [];

  // First pass: collect nodes in reverse post-order
  while (stack1.length > 0) {
    const node = stack1.pop();
    stack2.push(node);

    // Push left first, then right (opposite of what we want)
    if (node.left) stack1.push(node.left);
    if (node.right) stack1.push(node.right);
  }

  // Second pass: reverse to get post-order
  const result = [];
  while (stack2.length > 0) {
    result.push(stack2.pop().val);
  }

  return result;
}

This works because:

Stack1 generates: Root, Right, Left (reverse post-order)
Stack2 reverses it: Left, Right, Root (post-order)

Why in-order and pre-order don't need this

In-order and pre-order have a special property: We can process nodes "on the way down" or "in the middle" of the traversal.

Pre-order: Process immediately when we first see the node
In-order: Process when we can't go left anymore (natural pause point)

But post-order requires processing "on the way back up" after we've completely finished with children. This fundamentally requires tracking whether we're visiting for the first time (going down) or second time (coming back up).

The key realization

The extra complexity in post-order isn't a flaw - it's inherent to the traversal pattern. Post-order is the only traversal that requires complete knowledge of children before processing the parent. This makes it perfect for:

Calculating tree heights (need children's heights first)
Deleting nodes (delete children before parent)
Evaluating expression trees (evaluate operands before operators)

The visited flag or two-stack approach isn't unnecessary complexity - it's the minimum required to correctly implement the "children-first" guarantee that defines post-order traversal!