DFS Fundamentals
Deep dive into the Stack vs. Recursion implementation details.
Recursion is just a Stack
Often students get confused between Iterative (Stack) and Recursive DFS. It's important to realize they are identical in logic.
When you call dfs(node.left) inside a function, the computer pauses your current function, pushes its state (local variables) onto a system stack in memory, and starts executing the new call. When that finishes, it pops the state back and resumes.
Interactive Visualization
SAME PREORDER · DIFFERENT STACK
PUSH FRAME
call stack
TOP
On stack
1
Peak
1
result
Nothing appended yet
A new frame for 1 goes on the call stack (1 deep)
Next
Append 1. result = [1]
Tree
Legend & Complexity
The node being called or popped
On the stack: a call in progress, or a node waiting to be popped
Visited
Time
O(n)
Space
O(h) either way
Run the same preorder both ways on one tree. The column beside the tree is what each method is waiting on: frames of calls in progress, or nodes still to pop. The visit order comes out identical; the height of the stack does not.
Dry Run
Tree: [1, 2, 3]
| Step | Recursive call stack | Iterative stack (top last) | Appended |
|---|---|---|---|
| 1 | [dfs(1)] |
[1] → pop 1, push 3, push 2 → [3, 2] |
1 |
| 2 | [dfs(1), dfs(2)] |
pop 2 (no children) → [3] |
2 |
| 3 | [dfs(1)] — dfs(2) returned |
- | - |
| 4 | [dfs(1), dfs(3)] |
pop 3 (no children) → [] |
3 |
| End | [] |
[] |
[1, 2, 3] both ways |
The right child is pushed before the left one so that the left one is on top and popped first — that is what keeps the iterative order the same as the recursive one.
What is Stack Overflow?
Since recursion uses memory, if you go too deep (e.g., a tree with 10,000 nodes in a single line), the system stack runs out of space. This is a Stack Overflow.
- Recursion: Vulnerable to stack overflow on very deep trees.
- Iterative: Uses heap memory for the stack, so it can handle much deeper structures, limited only by total RAM.
The Base Case
Critical Rule: Every recursive function MUST have a base case (stopping condition).
For DFS on trees, it's usually:if (node == null) return;
Without this, your code will run infinitely until it crashes.
Both Versions
The same preorder written with recursion and with an explicit stack, in every language.
DFS Fundamentals Code
1function recursive(node, result) {2 if (!node) return;3 result.push(node.val);4 recursive(node.left, result);5 recursive(node.right, result);6}78function iterative(root) {9 const result = [];10 const stack = root ? [root] : [];11 while (stack.length > 0) {12 const node = stack.pop();13 result.push(node.val);14 if (node.right) {15 stack.push(node.right);16 }17 if (node.left) {18 stack.push(node.left);19 }20 }21 return result;22}