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.
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.
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.