Introduction to DFS

Depth-First Search (DFS) is a fundamental graph and tree traversal algorithm.

Imagine you are in a maze. A DFS strategy is to pick a path and keep walking until you hit a dead end. Once you hit a wall, you backtrack (retracing your steps) to the last intersection and try a different path. You explore depth first, diving as deep as possible before checking neighbors.

Consider a problem where you need to reach a specific node that is known to be very deep in a massive tree, or you need to generate a path from the root to a leaf.

"Given a binary tree, find a path that sums to X."

If the tree has height 1000, the target might be 1000 steps away.

Your instinct might be to check the closest nodes first (Level 1, then Level 2...). This is BFS.

While BFS finds the shortest path, it has a major drawback: Memory Usage.
To check Level 10, you must store ALL nodes of Level 9 in memory. For a full binary tree, the number of nodes doubles at each level. At depth 20, you might need to store 1 million nodes in your Queue just to take one more step! This can lead to Memory Limit Exceeded.

Imagine a queue exploding in size as the tree widens. BFS is like a tsunami explicitly flooding every inch of the map. DFS is like a single explorer with a rope, tracing one thin line at a time. The explorer (DFS) needs very little memory relative to the size of the world.

DFS logic utilizes a LIFO (Last-In, First-Out) structure.

1. Visit a node.
2. Push its children onto a stack (or call recursively).
3. Pop the most recently added child and visit it.

This means we always process the newest discovery first, leading us deeper and deeper until we run out of children (base case), triggering a backtrack.