Originally published on LeetCopilot Blog
Interviewers often ask you to rewrite a recursive solution iteratively—but most tutorials don’t show a systematic way to do it. Learn how to simulate recursion with a stack step by step.
You finally get a recursive solution working for a LeetCode problem. Then the interviewer smiles and says:
“Nice. Now can you do it iteratively—without recursion?”
Your mind goes blank. You know recursion uses the call stack somehow, but translating it into an explicit stack feels like black magic.
This guide explains, in a beginner-friendly way, how to convert a recursive solution to iterative on LeetCode using a stack. We’ll build a repeatable process you can apply to DFS on trees, graphs, and many backtracking-style problems.
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.
- The core steps: (1) identify the recursive state, (2) turn each call into a stack frame object, (3) push the initial frame, (4) loop while the stack is non-empty, (5) 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
Example: 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:
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.
- 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
rightthenleft, you processleftbeforeright.
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.
Example recursive post-order:
def postorder(root):
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
To convert this, we can store a flag saying whether we’ve already processed the children.
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 support you by stepping through both versions side by side and showing 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
If your recursion uses local variables or partial results, your stack frame must store them too. Otherwise, your iterative version won’t have the information it needs when a “call” resumes.
Mistake 2: Pushing children in the wrong order
Stack is LIFO. If your traversal order matters (e.g., pre-order vs in-order), get the push order right or you’ll visit nodes in the wrong sequence.
Mistake 3: Forgetting base cases
Just like recursion needs base cases, your loop needs:
- A way to stop (
while stack.length > 0).
- Guards against pushing null nodes.
Mistake 4: Mixing recursion and iteration unnecessarily
Trying to “half-convert” (some recursion, some stack) often creates confusion and bugs. Pick one style and stick with it for a given function.
FAQ
Q1: When do interviewers care about iterative vs recursive?
They often ask for iterative when recursion risks stack overflow, when they want to test your understanding of stacks, or as a follow-up to see if you can adapt your solution.
Q2: Do I always need to convert recursion to iteration?
No. Many interviewers are happy with recursion for trees and small graphs. But being able to convert is a strong signal of deeper understanding.
Q3: Is iterative always faster than recursive?
Big-O time is usually the same. Iterative solutions can avoid recursion overhead and stack limits, but clarity might suffer. In interviews, explain the trade-offs.
Q4: How can I systematically practice this skill?
Pick 5–10 recursive problems you've already solved (trees, graphs, backtracking). For each, write the stack-frame type and then the iterative version. For more guidance, see how to practice LeetCode without memorizing solutions.
Q5: What about backtracking with many parameters?
The same idea applies: each frame stores the parameters (path, index, sums, etc.). Sometimes this gets verbose; in those cases, recursion may be more readable, and it’s fine to explain that trade-off in an interview.
Conclusion
Converting a recursive solution to an iterative one on LeetCode is mostly about understanding what recursion already does for you—and then taking control of it.
The key steps:
- Identify the state each recursive call needs.
- Turn that state into an explicit stack frame.
- Replace “call / return” with “push / pop” in a loop.
With practice, you’ll stop fearing “Can you write this iteratively?” and start seeing it as an opportunity to show real mastery.
If you're looking for an AI assistant to help you master LeetCode patterns and prepare for coding interviews, check out LeetCopilot.