How to Convert a Recursive Solution to Iterative on LeetCode Using a Stack
Source: Dev.to
Originally published on LeetCopilot Blog
TL;DR
Recursion is just a function calling itself while the call stack remembers local state; converting to iterative means simulating that call stack with your own explicit stack.
Core steps
- Identify the recursive state.
- Turn each call into a stack‑frame object.
- Push the initial frame.
- Loop while the stack is non‑empty.
- Expand children by pushing new frames.
Visualizing the recursion tree and the stack side by side makes it much easier to see what information each frame needs.
Beginners often forget to store enough state in the frame (e.g., partial results or which child they’re on), or they push children in the wrong order and accidentally change traversal behavior.
With practice, you can treat recursion and iteration as interchangeable tools and feel confident when interviewers ask for an iterative version.
Beginner‑Friendly Explanation: What Recursion Really Does
The hidden stack
Every recursive call:
- Stores parameters and local variables in a frame.
- Jumps into the function body.
When it returns, the previous frame resumes where it left off.
You can picture it like this:
Call: dfs(root)
Stack (top at bottom):
[dfs(root)]
↳ calls dfs(root.left)
[dfs(root)] [dfs(root.left)]
↳ calls dfs(root.left.left)
[dfs(root)] [dfs(root.left)] [dfs(root.left.left)]When a base case hits, frames pop off the stack one by one.
Iterative idea in one sentence
To convert recursion to iteration, you take control of that stack—you decide what each frame stores, when you push frames, and how you process them in a loop.
Step‑by‑Step Framework: Convert Recursion to Iteration
We’ll use a classic recursive DFS on a binary tree as a running example.
Step 1: Write or inspect the recursive version
Pre‑order traversal (root → left → right):
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)Key observations
- State per call: the
rootnode reference. - Order: process current node, then left child, then right child.
Step 2: Decide what your “stack frame” holds
For this simple DFS, a frame only needs:
- The node itself.
In more complex recursions, a frame might need:
- Node + partial result.
- Node + index of which child we’re processing.
- Additional parameters like remaining target sum, depth, etc.
Step 3: Initialize the stack like the first call
The initial recursive call is preorder(root), so the initial stack in the iterative version should mimic that:
type Frame = { node: TreeNode | null };Push { node: root } to start.
Step 4: Loop while the stack is not empty
Instead of the call stack, you control the loop:
function preorderIterative(root: TreeNode | null): number[] {
const result: number[] = [];
if (!root) return result;
const stack: TreeNode[] = [root]; // frames can be just nodes here
while (stack.length > 0) {
const node = stack.pop()!;
result.push(node.val);
// Push children in reverse order (stack is LIFO)
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return result;
}The order of push calls preserves root → left → right: you pop the last‑pushed node first. By pushing right then left, you process left before right.
Visual Diagram: Recursion vs Iteration
Recursive DFS (pre‑order)
Call stack (top at bottom):
preorder(A)
preorder(B)
preorder(D)
preorder(E)
preorder(C)
preorder(F)Iterative DFS using a stack
Initial: stack = [A]
Pop A → visit A → push C, B stack = [C, B]
Pop B → visit B → push E, D stack = [C, E, D]
Pop D → visit D stack = [C, E]
Pop E → visit E stack = [C]
Pop C → visit C → push F stack = [F]
Pop F → visit F stack = []The order of visits is the same: A, B, D, E, C, F.
More Complex Case: Simulating “Post‑Order” with Explicit States
Some recursive functions do work after processing children (e.g., post‑order traversal or DP on trees). For those, each frame needs a bit of extra state.
Recursive post‑order
def postorder(root):
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]Iterative version with a visited flag
type Frame = {
node: TreeNode;
visited: boolean; // have we already pushed children?
};
function postorderIterative(root: TreeNode | null): number[] {
const result: number[] = [];
if (!root) return result;
const stack: Frame[] = [{ node: root, visited: false }];
while (stack.length > 0) {
const frame = stack.pop()!;
const { node, visited } = frame;
if (visited) {
// Children are done; now process the node
result.push(node.val);
} else {
// Post‑order: left, right, node
// Re‑push current node as visited
stack.push({ node, visited: true });
if (node.right) stack.push({ node: node.right, visited: false });
if (node.left) stack.push({ node: node.left, visited: false });
}
}
return result;
}This pattern—re‑push with a flag—is a powerful way to simulate “do work after children” without recursion.
Practical Preparation Strategies
Strategy 1: Practice on tree DFS variants
Start with:
- Pre‑order (root–left–right).
- In‑order (left–root–right).
- Post‑order (left–right–root).
For each:
- Write the recursive version.
- Identify the per‑call state.
- Implement the iterative stack version.
This builds a solid base for more complex conversions.
Strategy 2: Convert one real LeetCode problem per week
Pick a recursive solution you’ve already written and:
- Draw the recursion tree for a tiny example.
- Annotate what each frame needs to remember.
- Write the iterative version using a stack of frame objects.
Document the pattern in your notes or a DSA learning path so you can review it before interviews.
Strategy 3: Use tools to visualize stacks when stuck
When your iterative version doesn’t match the recursive one, tools like LeetCopilot can step through both versions side by side and show how the stack evolves, helping you see exactly where your simulation diverges.
Common Mistakes to Avoid
Mistake 1: Not storing enough state in the frame
(…the article continues with additional mistakes…)