Explore a path all the way to the end, then backtrack. Implemented with recursion (function call stack) or an explicit stack.

Data Flow

tree:

       1
      / \
     2   3
    / \
   4   5

DFS pre-order: 1, 2, 4, 5, 3

When to use

• Path exists? (graph connectivity, tree path sum).
• Topological sort (paired with post-order).
• Cycle detection.
• Generate all combinations / permutations (with backtracking).

Code (path sum)

def has_path_sum(node, target):
    if not node: return False
    if not node.left and not node.right:
        return node.val == target
    return (has_path_sum(node.left,  target - node.val) or
            has_path_sum(node.right, target - node.val))

Pitfalls

• Forgetting the base case -> infinite recursion / stack overflow.
• Mutating state without backtracking when you should.

Analogy

Exploring a maze by always turning right: walk until you hit a dead end, return, then try the next path. You finish before exhausting any branches.

Interview tip: State the base case first when writing DFS. Then the recursion. If you cannot articulate the base case, don’t start coding.