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 - exploring all possible configurations or states of a problem
  • Puzzle solving (8-puzzle, Rubik's cube, Sudoku)
  • Game state exploration (chess moves, tic-tac-toe outcomes)
  • Path finding with constraints (mazes with keys/doors)
  • Configuration problems (satisfiability, constraint satisfaction)
  • The explicit stack gives you full visibility into the search path, allowing you to track visited states, implement custom pruning strategies, or extract the actual solution path when a goal state is found
• 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

Pausable File System Search: You're building a file search feature for a cloud storage system with millions of files organized in a deep folder tree. The search needs to:

1. Find all files matching a pattern (e.g., "*.pdf")
2. Pause every 1000 files to update a progress bar and check if user cancelled
3. Resume exactly where it left off if user wants to continue
4. Return the complete path for each matching file
5. Avoid stack overflow on deeply nested folders (thousands of levels deep)

Given this folder structure:

Root/
├── Documents/
│   ├── reports/
│   │   ├── report1.pdf  ✓ match
│   │   └── data.txt
│   └── archive/
│       └── old.pdf      ✓ match
└── Downloads/
    └── ebook.pdf        ✓ match

Why recursion won't work:

• Can't pause mid-recursion - recursive calls block until complete
• Can't inspect current path - call stack is hidden
• Stack overflow risk - deeply nested folders exhaust memory
• Can't resume - must start over if interrupted

Answer: Iterative DFS gives you an explicit stack you can pause, inspect (to build file paths), and resume - something impossible with recursion's hidden call stack.

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 searching through a filing cabinet:

• Recursive DFS: Following breadcrumbs that disappear behind you - you can only see where you are now, not where you've been or what's left to explore. If you need to stop, you lose all progress.
• Iterative DFS: Having a visible bookmark list - you can see exactly what folders remain to search, pause anytime, check your progress, and resume from the exact same spot later

How the Stack Operations Work

The Core Pattern - "Manually managing the call stack"

When traversing with a stack:

1. Push nodes onto the stack (like making a recursive call)

   • Saves nodes for later exploration
   • Order matters: last pushed = first processed (LIFO)

2. Pop nodes from the stack (like returning from a recursive call)

   • Retrieves the next node to work on
   • Simulates "going back up" after exploring a subtree

3. Process nodes at the right moment (depends on traversal order)

   • Pre-order: Process immediately when first encountered (before pushing children)
   • In-order: Process when can't go left anymore (between left and right exploration)
   • Post-order: Process only after both children are done (on second visit)
   • File search: Process when popped (checking if it matches the pattern)

4. Track state if needed (for complex traversals)

   • Post-order: Need "visited" flag to know if this is first or second visit
   • File search: Track full path by storing [node, path] pairs in stack
   • Graph traversal: Track visited nodes to avoid cycles
   • Pausable search: Track progress counts, batch limits, completion status

The Three Classic Tree Traversals

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

Process pattern:

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

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

Process pattern:

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

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

Process pattern:

1. Track whether we've visited children
2. First visit: push children onto stack
3. Second visit: process the node
4. 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 maintaining a simple "to-do list" of nodes to explore. The stack is just that list. At each step, you grab the next item from the list (pop), do your work on it, and add any new items you discover to the list (push). This direct mental model - "work through a to-do list" - is simpler than thinking about recursion, and naturally gives you the control to pause, inspect progress, or track custom state that recursion can't provide.

Decision Framework

At every iteration, you ask simple questions to decide what to do next. Here's the pattern for our file search example:

File Search Decision Flow (simplest pattern):

Pop next item from stack
    ↓
Is it a file or folder?
    ↓
┌───────────────┬───────────────┐
│    FILE       │    FOLDER     │
└───────────────┴───────────────┘
        ↓               ↓
  Does it match?   Add children
        ↓          to stack
  Save if yes         ↓
        ↓         Continue loop
   Continue loop

Questions at each step:

1. "Should I pause?" → Check if processed enough nodes
2. "Is this a file or folder?" → Determines what to do
3. "Does it match pattern?" → Only for files
4. "What children to explore?" → Push them to stack

---

For Classic Tree Traversals, the pattern changes based on when you want to process nodes:

Pre-order (process node → explore children):

Visit node
    ↓
Process NOW (collect value)
    ↓
Push right child (save for later)
    ↓
Move to left child (explore immediately)

Use case: Copy tree structure, serialize data

In-order (explore left → process node → explore right):

Can I go left?
    ↓
┌─────YES─────┬─────NO─────┐
│             │            │
Push current  Pop & process
Go left       Then go right

Use case: Get sorted values from BST

Post-order (explore children → process node):

First visit to node?
    ↓
┌─────YES─────┬─────NO─────┐
│             │            │
Push node     Process NOW
(mark visited)(children done)
Push children

Use case: Calculate tree size, delete nodes

The Core Decision: Every traversal boils down to "When do I process this node relative to exploring its children?" The explicit stack lets you control this timing precisely.

Code

Let's explore all three traversal types with practical examples. The key difference is when we process each node relative to exploring its children.

Pre-Order Traversal: Process → Explore

Pattern: Process the current node BEFORE exploring children Use case: Searching, copying trees, prefix expression evaluation

// Simple binary tree node for demonstration
type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};

// === PRE-ORDER: Process node BEFORE children ===
function preorderIterative(root: TreeNode | null): Array<number> {
  if (root == null) return [];

  const result: Array<number> = [];
  const stack: Array<TreeNode> = [root];

  while (stack.length > 0) {
    const node = stack.pop();
    if (node == null) continue;

    // DECISION FRAMEWORK: Process IMMEDIATELY when we see the node
    result.push(node.val); // Process parent FIRST

    // Then add children for future exploration
    // Push right first so left is processed first (LIFO)
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }

  return result;
}

// Example tree:     1
//                  /   \
//                 2     3
//                / \
//               4   5
// Pre-order: [1, 2, 4, 5, 3] (Root → Left → Right)

Real-World Example: File System Search

// Definition for a file system node
class FileNode {
  name: string;
  isFile: boolean;
  children: Array<FileNode>;

  constructor(
    name: string,
    isFile: boolean = false,
    children: Array<FileNode> = []
  ) {
    this.name = name;
    this.isFile = isFile;
    this.children = children; // Array of FileNode (empty if isFile is true)
  }
}

// Type definitions for search results and progress
type SearchStatus = "paused" | "complete" | "already_complete";

type PausedSearchResult = {
  status: "paused";
  processed: number;
  matches: number;
  stackDepth: number;
};

type CompleteSearchResult = {
  status: "complete" | "already_complete";
  processed: number;
  matches: number;
  results: Array<string>;
};

type SearchResult = PausedSearchResult | CompleteSearchResult;

type ProgressInfo = {
  nodesProcessed: number;
  matchesFound: number;
  remainingInStack: number;
  isComplete: boolean;
};

// Stack entry type: object with node and its full path from root
type StackEntry = {
  node: FileNode;
  path: string; // Full path from root (e.g., "Root/Documents/reports")
};

// === PAUSABLE FILE SEARCH ===
// Searches for files matching a pattern, with ability to pause and resume
// Uses pre-order traversal: processes each node before exploring its children
class PausableFileSearch {
  private root: FileNode;
  private pattern: string;
  private searchStack: Array<StackEntry>;
  private matchingFiles: Array<string>;
  private totalNodesProcessed: number;
  private isComplete: boolean;

  constructor(root: FileNode, pattern: string) {
    this.root = root;
    this.pattern = pattern;

    // Explicit stack stores objects with node and full path from root
    // Initially, the root's path is just its name
    this.searchStack = [{ node: root, path: root.name }];

    // Search results and progress tracking
    this.matchingFiles = [];
    this.totalNodesProcessed = 0;
    this.isComplete = false;
  }

  // Traverse the tree, processing nodes and expanding to children
  // Continues until we hit the node limit or complete the traversal
  traverse(nodeLimit: number = 1000): SearchResult {
    let nodesProcessedThisCall = 0;

    while (true) {
      // DECISION FRAMEWORK: Is traversal complete?
      const isStackEmpty = this.searchStack.length === 0;

      if (isStackEmpty) {
        // No more nodes to explore - search is complete
        this.isComplete = true;
        return {
          status: "complete",
          processed: this.totalNodesProcessed,
          matches: this.matchingFiles.length,
          results: this.matchingFiles,
        };
      }

      // DECISION FRAMEWORK: Should we pause?
      const shouldPause = nodesProcessedThisCall >= nodeLimit;

      if (shouldPause) {
        // Pause here - stack preserves our exact position
        return {
          status: "paused",
          processed: this.totalNodesProcessed,
          matches: this.matchingFiles.length,
          stackDepth: this.searchStack.length,
        };
      }

      // Pop next node and its full path from stack
      // We already verified stack is non-empty above
      const stackEntry = this.searchStack.pop();

      // This should never happen due to the isEmpty check above,
      // but TypeScript doesn't understand the control flow
      if (stackEntry == null) {
        throw new Error("Unexpected: stack was empty after non-empty check");
      }

      const currentNode = stackEntry.node;
      const currentPath = stackEntry.path;

      nodesProcessedThisCall++;
      this.totalNodesProcessed++;

      // PRE-ORDER: Process current node BEFORE exploring children
      // DECISION FRAMEWORK: Is this a file or folder?
      if (currentNode.isFile) {
        // Check if file matches pattern
        const matchesPattern = currentNode.name.endsWith(this.pattern);

        if (matchesPattern) {
          this.matchingFiles.push(currentPath);
        }
      } else {
        // It's a folder - add children to stack for FUTURE exploration
        // This happens AFTER processing the current node (pre-order)
        // Push in reverse order so we process left-to-right
        const children = currentNode.children;

        for (let i = children.length - 1; i >= 0; i--) {
          const childNode = children[i];
          const childPath = `${currentPath}/${childNode.name}`;

          // Push child with its full path
          this.searchStack.push({ node: childNode, path: childPath });
        }
      }
    }
  }

  // Resume traversal from where we paused
  resume(nodeLimit: number = 1000): SearchResult {
    const canResume = !this.isComplete && this.searchStack.length > 0;

    if (canResume) {
      return this.traverse(nodeLimit);
    }

    return {
      status: "already_complete",
      processed: this.totalNodesProcessed,
      matches: this.matchingFiles.length,
      results: this.matchingFiles,
    };
  }

  // Get current progress
  getProgress(): ProgressInfo {
    return {
      nodesProcessed: this.totalNodesProcessed,
      matchesFound: this.matchingFiles.length,
      remainingInStack: this.searchStack.length,
      isComplete: this.isComplete,
    };
  }
}

// === EXAMPLE USAGE: File System Search ===

// Build the file system tree from the example
const fileSystem = new FileNode("Root", false, [
  new FileNode("Documents", false, [
    new FileNode("reports", false, [
      new FileNode("report1.pdf", true),
      new FileNode("data.txt", true),
    ]),
    new FileNode("archive", false, [new FileNode("old.pdf", true)]),
  ]),
  new FileNode("Downloads", false, [new FileNode("ebook.pdf", true)]),
]);

// Create search for PDF files
const search = new PausableFileSearch(fileSystem, ".pdf");

// First traversal: process 2 nodes then pause
let result = search.traverse(2);
console.log(`Status: ${result.status}`);
console.log(`Processed: ${result.processed} nodes`);
console.log(`Matches found: ${result.matches}`);

// Type guard for paused result
if (result.status === "paused") {
  console.log(`Stack depth: ${result.stackDepth} (can resume from here)`);
}
// Check progress
console.log(search.getProgress());

// Resume: traverse 3 more nodes then pause
result = search.resume(3);
console.log(`Status: ${result.status}`);
console.log(`Processed: ${result.processed} nodes total`);
console.log(`Matches found: ${result.matches}`);

// Resume until complete
result = search.resume(1000);
console.log(`Status: ${result.status}`);
console.log(`Total nodes processed: ${result.processed}`);
console.log(`Total matches: ${result.matches}`);

// Type guard for complete result
if (result.status === "complete" || result.status === "already_complete") {
  console.log("\nMatching files:");
  result.results.forEach((path) => console.log(`  ${path}`));
}

In-Order Traversal: Explore Left → Process → Explore Right

Pattern: Process the node BETWEEN exploring left and right children Use case: Binary search trees (gives sorted output), expression trees

// === IN-ORDER: Process node BETWEEN children ===
function inorderIterative(root: TreeNode | null): Array<number> {
  if (root == null) return [];

  const result: Array<number> = [];
  const stack: Array<TreeNode> = [];
  let current: TreeNode | null = root;

  // Helper function to make processing explicit.
  function processNode(value: number) {
    result.push(value); // or some other logic
  }

  while (current != null || stack.length > 0) {
    // DECISION FRAMEWORK: Go as far left as possible first
    while (current != null) {
      stack.push(current); // Stack operation: save for later
      current = current.left;
    }

    // Process node when we can't go left anymore
    const node = stack.pop(); // Stack operation: retrieve saved node
    if (node != null) {
      processNode(node.val); // Process BETWEEN left and right (NOT a stack operation)
      current = node.right; // Now explore right subtree
    }
  }

  return result;
}

// Example BST:      4
//                  /   \
//                 2     6
//                / \   / \
//               1   3 5   7
// In-order: [1, 2, 3, 4, 5, 6, 7] (Sorted!)

Real-World Example: Database Index Traversal

What we're doing: Imagine you have a database table with user records, and you want to retrieve all users in alphabetical order by name. Instead of scanning the entire table and sorting, databases use a Binary Search Tree (BST) index to keep names organized.

The problem: Given a BST index on the "name" column, retrieve all user records in alphabetical order.

Example database table (Users):

| Record ID | Name | Email | | --------- | ------- | --------------- | | 101 | Charlie | charlie@ex.com | | 102 | Alice | alice@ex.com | | 103 | David | david@ex.com | | 104 | Bob | bob@ex.com | | 105 | Alice | alice2@ex.com |

Index tree built on "Name" column:

       "Charlie" → [101]
       /              \
"Alice" → [102,105]   "David" → [103]
      \
    "Bob" → [104]

Each node stores:

• key: The name (indexed value)
• recordIds: Array of row IDs with that name (e.g., two Alices: rows 102 and 105)

Goal: Use in-order traversal to get all names alphabetically: Alice → Bob → Charlie → David

// Binary Search Tree for database index
class IndexNode {
  key: string; // The indexed value (e.g., user name "Alice")
  recordIds: Array<number>; // IDs of all database rows with this key value
  left: IndexNode | null = null;
  right: IndexNode | null = null;

  constructor(key: string, recordId: number) {
    this.key = key;
    this.recordIds = [recordId]; // Initially contains one record ID
  }
}

// Find all records in alphabetical order
// root: The root of an already-built BST index
// Returns: Map of names to record IDs, in alphabetical order
function getAllRecordsInOrder(
  root: IndexNode | null // BST already maintains sorted order by structure
): Map<string, Array<number>> {
  const orderedRecords = new Map<string, Array<number>>();
  const stack: Array<IndexNode> = [];
  let current = root;

  while (current != null || stack.length > 0) {
    // Navigate to leftmost node
    while (current != null) {
      stack.push(current);
      current = current.left;
    }

    // Process node (in sorted order)
    const node = stack.pop();
    if (node != null) {
      orderedRecords.set(node.key, node.recordIds);
      current = node.right;
    }
  }

  return orderedRecords;
}

// Example index tree for names:
//        "Charlie"
//        /        \
//    "Alice"    "David"
//       \
//      "Bob"
//
// In-order traversal gives: Alice → Bob → Charlie → David (alphabetical!)

Post-Order Traversal: Explore → Process

Pattern: Process the node AFTER exploring all children Use case: Calculating sizes, deleting trees, postfix expression evaluation

// === POST-ORDER: Process node AFTER children ===
function postorderIterative(root: TreeNode | null): Array<number> {
  if (root == null) return [];

  const result: Array<number> = [];
  const stack: Array<{ node: TreeNode; visited: boolean }> = [
    { node: root, visited: false },
  ];

  while (stack.length > 0) {
    const entry = stack[stack.length - 1]; // Peek at top

    // DECISION FRAMEWORK: Have we visited this node's children yet?
    if (!entry.visited) {
      // First time seeing this node - mark as visited and add children
      entry.visited = true;

      // Add children (right first so left is processed first)
      if (entry.node.right) {
        stack.push({ node: entry.node.right, visited: false });
      }
      if (entry.node.left) {
        stack.push({ node: entry.node.left, visited: false });
      }
    } else {
      // Second time seeing this node - children are done, process it
      stack.pop();
      result.push(entry.node.val); // Process AFTER children
    }
  }

  return result;
}

// Example tree:     1
//                  /   \
//                 2     3
//                / \
//               4   5
// Post-order: [4, 5, 2, 3, 1] (Left → Right → Root)

Real-World Example: Calculate Directory Sizes

// File system node with size
class FileSystemNode {
  name: string;
  isFile: boolean;
  size: number; // For files: actual size. For dirs: calculated from children
  children: Array<FileSystemNode>;

  constructor(name: string, isFile: boolean, size: number = 0) {
    this.name = name;
    this.isFile = isFile;
    this.size = size;
    this.children = [];
  }
}

// Calculate total size of each directory (must process children first!)
function calculateDirectorySizes(root: FileSystemNode): Map<string, number> {
  const directorySizes = new Map<string, number>();
  const stack: Array<{
    node: FileSystemNode;
    path: string;
    visited: boolean;
  }> = [{ node: root, path: root.name, visited: false }];

  while (stack.length > 0) {
    const entry = stack[stack.length - 1];

    if (!entry.visited) {
      // First visit: add children to stack
      entry.visited = true;

      if (!entry.node.isFile) {
        // Add all children for processing
        for (const child of entry.node.children) {
          stack.push({
            node: child,
            path: `${entry.path}/${child.name}`,
            visited: false,
          });
        }
      }
    } else {
      // Second visit: children are processed, calculate this node's size
      stack.pop();

      if (entry.node.isFile) {
        // File: just use its size
        // Parent directory will sum this up
      } else {
        // Directory: sum up all children's sizes
        let totalSize = 0;
        for (const child of entry.node.children) {
          if (child.isFile) {
            // Files: use the file's direct size
            totalSize += child.size;
          } else {
            // Subdirectories: retrieve the ALREADY CALCULATED total
            // Post-order guarantees this child directory was fully processed
            // earlier (popped from stack before its parent), so its complete
            // size is already stored in the map. We're not double counting -
            // we're using the pre-calculated total instead of recalculating.
            const childPath = `${entry.path}/${child.name}`;
            const childDirectoryTotal = directorySizes.get(childPath) || 0;
            totalSize += childDirectoryTotal;
          }
        }

        // Store THIS directory's total size in the map
        // (this total will be used when THIS directory appears as a child)
        directorySizes.set(entry.path, totalSize);
        entry.node.size = totalSize; // Update the node itself
      }
    }
  }

  return directorySizes;
}

// Example file system:
//      Root/
//      ├── docs/ (30KB total)
//      │   ├── file1.txt (10KB)
//      │   └── file2.txt (20KB)
//      └── images/ (150KB total)
//          ├── pic1.jpg (100KB)
//          └── pic2.jpg (50KB)
//
// Post-order ensures we calculate docs/ and images/ sizes
// BEFORE calculating Root/ size (180KB)

Summary: When to Use Each Traversal

| Traversal | When to Process | Use Cases | | -------------- | -------------------- | --------------------------------------- | | Pre-order | BEFORE children | Searching, copying, serialization | | In-order | BETWEEN left & right | Sorted retrieval from BST | | Post-order | AFTER all children | Size calculation, cleanup, dependencies |

The beauty of iterative DFS is that by managing the stack explicitly, you have complete control over the traversal order - just change when you process nodes relative to when you explore their children!

Doubt buster

Common doubt: "Can iterative DFS truly handle everything that recursive DFS can? More broadly, can iteration replace ALL recursive logic, not just DFS? Or are there cases where recursion is fundamentally necessary?"

The Fundamental Equivalence: Can iteration replace ALL recursion?

Yes, theoretically ANY recursive algorithm can be converted to an iterative one. This isn't specific to DFS - it's a fundamental principle in computer science.

Why this is universally true: Every recursive algorithm uses the call stack. An iterative version just uses an explicit stack data structure instead. Since you can always create your own stack, you can always replace recursion with iteration.

This applies to ALL recursive algorithms:

• Tree/Graph traversals (DFS, BFS variations)
• Divide and conquer (quicksort, merge sort, binary search)
• Backtracking (N-Queens, Sudoku solver, permutations)
• Dynamic programming (can be top-down recursive or bottom-up iterative)
• Mathematical recursion (Fibonacci, factorial, Towers of Hanoi)

For DFS specifically, here's why the equivalence works:

When you make a recursive call, the system does two things automatically:

1. Saves local variables to the call stack
2. Remembers where to return when the call completes

With iterative DFS, you manually do these same two things:

1. Save state in your explicit stack (store variables in stack entries)
2. Control execution flow with your loop and stack operations

Proof by example - here's a recursive function and its iterative equivalent:

// RECURSIVE: Calculate tree height
function heightRecursive(node: TreeNode | null): number {
  if (node == null) return 0;

  // Recursive calls save these calculations on call stack
  const leftHeight = heightRecursive(node.left);
  const rightHeight = heightRecursive(node.right);

  return Math.max(leftHeight, rightHeight) + 1;
}

// ITERATIVE: Same calculation, explicit stack
function heightIterative(root: TreeNode | null): number {
  if (root == null) return 0;

  // We need to store PARTIAL RESULTS - this is what makes it complex
  type StackEntry = {
    node: TreeNode;
    phase: "initial" | "left_done" | "right_done";
    leftHeight?: number; // Store result from left subtree
    rightHeight?: number; // Store result from right subtree
  };

  const stack: Array<StackEntry> = [{ node: root, phase: "initial" }];
  let finalHeight = 0;

  while (stack.length > 0) {
    const entry = stack[stack.length - 1]; // Peek

    if (entry.phase === "initial") {
      // First visit - explore left child
      entry.phase = "left_done";
      if (entry.node.left) {
        stack.push({ node: entry.node.left, phase: "initial" });
      } else {
        entry.leftHeight = 0; // No left child = height 0
      }
    } else if (entry.phase === "left_done") {
      // Left is done - capture its result and explore right
      if (entry.node.left) {
        // Pop left child's result from stack
        const leftResult = stack.pop();
        if (leftResult != null) {
          entry.leftHeight = finalHeight; // Save left's calculated height
        }
      }
      entry.phase = "right_done";
      if (entry.node.right) {
        stack.push({ node: entry.node.right, phase: "initial" });
      } else {
        entry.rightHeight = 0;
      }
    } else {
      // Both children done - calculate this node's height
      if (entry.node.right) {
        stack.pop(); // Pop right child
        entry.rightHeight = finalHeight;
      }
      const leftH = entry.leftHeight ?? 0;
      const rightH = entry.rightHeight ?? 0;
      finalHeight = Math.max(leftH, rightH) + 1;
      stack.pop(); // Pop this node
    }
  }

  return finalHeight;
}

The takeaway: Yes, you CAN convert any recursive DFS to iterative. But look at the complexity difference!

Beyond DFS: Other Recursive Algorithms Converted to Iterative

To prove this isn't DFS-specific, here are other classic recursive algorithms with their iterative equivalents:

Example 1: Quicksort (Divide and Conquer)

// RECURSIVE: Elegant 15 lines
function quicksortRecursive(arr: Array<number>, low: number, high: number) {
  if (low >= high) return;

  const pivot = partition(arr, low, high);
  quicksortRecursive(arr, low, pivot - 1); // Sort left
  quicksortRecursive(arr, pivot + 1, high); // Sort right
}

// ITERATIVE: Need explicit stack to track ranges
function quicksortIterative(arr: Array<number>) {
  const stack: Array<[number, number]> = [[0, arr.length - 1]];

  while (stack.length > 0) {
    const range = stack.pop();
    if (range == null) continue;

    const [low, high] = range;
    if (low >= high) continue;

    const pivot = partition(arr, low, high);

    // Push both ranges to stack (replacing recursive calls)
    stack.push([low, pivot - 1]);
    stack.push([pivot + 1, high]);
  }
}

Example 2: Fibonacci (Mathematical Recursion)

// RECURSIVE: Natural mathematical definition
function fibRecursive(n: number): number {
  if (n <= 1) return n;
  return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// ITERATIVE: Bottom-up approach (actually more efficient!)
function fibIterative(n: number): number {
  if (n <= 1) return n;

  let prev = 0;
  let curr = 1;

  for (let i = 2; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }

  return curr;
}

Example 3: Backtracking - Generate all permutations

// RECURSIVE: Clean backtracking pattern
function permuteRecursive(nums: Array<number>): Array<Array<number>> {
  const result: Array<Array<number>> = [];

  function backtrack(current: Array<number>, remaining: Array<number>) {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }

    for (let i = 0; i < remaining.length; i++) {
      backtrack(
        [...current, remaining[i]],
        [...remaining.slice(0, i), ...remaining.slice(i + 1)]
      );
    }
  }

  backtrack([], nums);
  return result;
}

// ITERATIVE: Complex state management
function permuteIterative(nums: Array<number>): Array<Array<number>> {
  const result: Array<Array<number>> = [];
  const stack: Array<{
    current: Array<number>;
    remaining: Array<number>;
  }> = [{ current: [], remaining: nums }];

  while (stack.length > 0) {
    const state = stack.pop();
    if (state == null) continue;

    if (state.remaining.length === 0) {
      result.push(state.current);
      continue;
    }

    // Push all possible next states
    for (let i = state.remaining.length - 1; i >= 0; i--) {
      stack.push({
        current: [...state.current, state.remaining[i]],
        remaining: [
          ...state.remaining.slice(0, i),
          ...state.remaining.slice(i + 1),
        ],
      });
    }
  }

  return result;
}

Key observation: In every case, you CAN convert recursion to iteration, but the recursive version is typically cleaner and more intuitive. The iterative version requires manually managing state that recursion handles automatically.

When Should You Use Each?

The equivalence doesn't mean iterative is always better. Here's the practical decision framework:

Use RECURSIVE DFS when:

• ✅ Natural fit - Problem is inherently recursive (tree operations, divide-and-conquer)
• ✅ Simplicity matters - Cleaner, easier to understand and maintain
• ✅ No stack overflow risk - Tree depth is reasonable (< 1000 levels typically safe)
• ✅ Return values needed - You need to collect and combine results from subtrees
• ✅ Standard traversals - Basic pre/in/post-order where recursion is clearest

Example: Recursion is perfect here

// Finding max value in tree - recursion is naturally clean
function findMax(node: TreeNode | null): number {
  if (node == null) return -Infinity;
  return Math.max(node.val, findMax(node.left), findMax(node.right));
}

// Iterative version would need complex state tracking - not worth it!

Use ITERATIVE DFS when:

• ✅ Stack overflow risk - Very deep trees (millions of nodes, thousands of levels)
• ✅ Need to pause/resume - Long-running search that needs to be paused and resumed later
• ✅ Stack inspection needed - Must see the current path or traversal state
• ✅ Custom control flow - Need to backtrack, skip subtrees, or modify traversal mid-execution
• ✅ Memory constraints - System call stack is limited, but heap memory is available

Example: Iterative is necessary here

// Pausable search - impossible with recursion
class PausableSearch {
  private stack: Array<StackEntry>;

  search(limit: number) {
    while (this.stack.length > 0 && processed < limit) {
      // Process nodes...
      // Can pause here and resume later!
    }
  }
}

The Real-World Rule of Thumb

Default to recursion for most algorithms unless you have a specific reason not to:

• 95% of problems → Use recursion (simpler, cleaner, more maintainable)
• 5% with special needs → Use iterative (stack overflow risk, pause/resume, explicit state inspection)

Recursion is not inferior - it's the natural, preferred solution for most recursive problems. The iterative approach is a powerful tool for when recursion's limitations become actual problems, not a "better" approach you should always use.

Why recursion is usually preferred:

• Matches the problem structure - Tree traversal, divide-and-conquer, and backtracking are inherently recursive concepts
• Self-documenting code - Recursive code often reads like the mathematical definition or problem description
• Less error-prone - No manual stack management means fewer bugs
• Compiler optimizations - Modern compilers can optimize tail-recursive functions automatically

When iteration becomes necessary:

• Stack depth limits - System call stack is typically limited to thousands of frames
• External constraints - Need to save/restore state across program restarts
• Performance critical - Eliminating function call overhead (though compilers often do this)
• Educational purposes - Understanding what recursion does under the hood

Why the Complexity Difference?

The recursive version is simpler because the language runtime handles state management:

• Call stack automatically saves local variables
• Return values automatically flow back up
• Execution resumes at the right place automatically

The iterative version must manually implement all of this:

• Explicitly save variables in stack entries
• Manually track what phase of processing you're in
• Write code to handle each phase transition

But What If Iteration IS Cleaner?

Great question: "If the main advantage of recursion is clarity, wouldn't iteration be better when IT'S also clean?"

Yes, absolutely! When an iterative solution is equally clean and intuitive, it's often BETTER than recursion because you get:

• ✅ No stack overflow risk
• ✅ Explicit control over execution
• ✅ Easier debugging (can inspect stack directly)
• ✅ Better performance (no function call overhead)

Example where iteration is naturally cleaner: Fibonacci

// RECURSIVE: Matches math definition but exponential time complexity
function fibRecursive(n: number): number {
  if (n <= 1) return n;
  return fibRecursive(n - 1) + fibRecursive(n - 2); // Recalculates same values!
}

// ITERATIVE: Actually simpler AND more efficient
function fibIterative(n: number): number {
  if (n <= 1) return n;

  let prev = 0,
    curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr]; // Clean single-line update
  }
  return curr;
}

In this case, iteration is superior - it's simpler, more readable, AND more efficient.

Other cases where iteration is naturally clean:

1. Tail-recursive functions - These are just loops in disguise:

   // Tail recursion: Last operation is the recursive call
   function sumRecursive(n: number, acc: number = 0): number {
     if (n === 0) return acc;
     return sumRecursive(n - 1, acc + n); // Tail call
   }
   
   // Iteration is equally clear and avoids stack frames
   function sumIterative(n: number): number {
     let sum = 0;
     for (let i = 1; i <= n; i++) {
       sum += i;
     }
     return sum;
   }

2. Bottom-up dynamic programming - Iteration is more natural:

   // Building solutions from base cases up is naturally iterative
   function climbStairs(n: number): number {
     if (n <= 2) return n;
   
     let prev = 1,
       curr = 2;
     for (let i = 3; i <= n; i++) {
       [prev, curr] = [curr, prev + curr];
     }
     return curr;
   }

3. Simple linear traversals - Loop is clearer than recursion:

   // Array sum - iteration is more natural
   function sumArray(arr: Array<number>): number {
     let sum = 0;
     for (const num of arr) {
       sum += num;
     }
     return sum;
   }

The key principle: Use whichever is cleaner for the specific problem.

Most recursive problems (trees, divide-and-conquer, backtracking) are cleaner with recursion because they involve:

• Multiple recursive calls
• Combining return values from subtrees
• Natural hierarchical structure

But when iteration is equally or more intuitive (tail recursion, linear traversal, bottom-up DP), prefer iteration for the benefits above.

Bottom line:

• Can iteration replace ALL recursion (not just DFS)? Yes, theoretically any recursive algorithm can be converted to iterative.
• Should you always use iteration instead of recursion? No, absolutely not.
• Should you always use recursion instead of iteration? No, absolutely not.
• The real rule: Use whichever approach is cleaner and more intuitive for your specific problem. In practice, this means recursion for trees/graphs/backtracking (cleaner), and iteration for tail-recursive patterns/linear traversals/bottom-up DP (equally or more clear).