Tree Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. When applied to trees, it systematically visits every node.

Core Idea:

DFS for trees starts at the root node (or a chosen arbitrary node) and explores as far as possible along each branch before backtracking. It uses a stack (implicitly through recursion or explicitly with a stack data structure) to keep track of nodes to visit. The process involves visiting a node, then recursively (or iteratively) visiting its children.

Common Scenarios & How it Works:

There are three main ways to traverse a tree using DFS:

  1. Inorder Traversal (Left -> Root -> Right):
    • Recursively traverse the left subtree.
    • Visit the current node.
    • Recursively traverse the right subtree.
    • Use Case: For Binary Search Trees (BSTs), this traversal visits nodes in ascending order.
  2. Preorder Traversal (Root -> Left -> Right):
    • Visit the current node.
    • Recursively traverse the left subtree.
    • Recursively traverse the right subtree.
    • Use Case: Useful for creating a copy of the tree, or when you need to process the root before its children (e.g., expression trees).
  3. Postorder Traversal (Left -> Right -> Root):
    • Recursively traverse the left subtree.
    • Recursively traverse the right subtree.
    • Visit the current node.
    • Use Case: Useful for deleting nodes in a tree (process children before the parent), or when you need to process children before the root (e.g., evaluating an expression tree).

Other Applications:

  • Pathfinding: Finding a path between two nodes in a tree.
  • Cycle Detection (in graphs, not typically trees as trees are acyclic): DFS can detect cycles in a graph.
  • Topological Sort (for Directed Acyclic Graphs - DAGs): While trees are a type of DAG, topological sort is more commonly discussed in the context of general DAGs.
  • Solving Puzzles: Many maze-solving or game-tree evaluation algorithms use DFS.
  • Checking Connectivity: Determining if all nodes are reachable from a starting node.

Advantages:

  • Simplicity: The recursive implementation of DFS is often very intuitive and easy to write.
  • Space Efficiency (in some cases): If the tree is very deep, the recursion stack can grow large. However, for wide trees, it can be more space-efficient than Breadth-First Search (BFS) as it only needs to store nodes along the current path.
  • Finding a Path: DFS is good for finding a path between two nodes, as it goes deep into the tree quickly.

When to Use:

  • When you need to visit every node in a tree.
  • For problems involving tree traversals in a specific order (Inorder, Preorder, Postorder).
  • When trying to find a path from a root to a leaf that satisfies certain conditions.
  • When the problem involves exploring one branch of a tree as deeply as possible.
  • If memory is a concern for very wide trees (compared to BFS).

Example LeetCode Problems:

  1. (#94) Binary Tree Inorder Traversal
  2. (#144) Binary Tree Preorder Traversal
  3. (#145) Binary Tree Postorder Traversal
  4. (#100) Same Tree
  5. (#101) Symmetric Tree (Can be solved with DFS by checking mirrored subtrees)
  6. (#104) Maximum Depth of Binary Tree
  7. (#112) Path Sum
  8. (#113) Path Sum II
  9. (#129) Sum Root to Leaf Numbers
  10. (#226) Invert Binary Tree