Tree Depth-First Search Pattern

When to use Tree Depth-First Search

• The problem asks about root-to-leaf paths, longest path, or any path-sum target.
• You need to compute a value at every subtree (size, height, max, sum) and combine it with the parent's value.
• You need to validate a tree property (is BST, is balanced, is symmetric) that requires checking left and right subtrees.
• You need to serialize, deserialize, or compare two trees structurally.
• Pre-order, in-order, or post-order traversal yields the answer directly (BSTs and in-order are a classic pair).

Template

function pathSum(root, target) {
  if (root === null) return false;
  function dfs(node, remaining) {
    if (node === null) return false;
    if (node.left === null && node.right === null) {
      return remaining === node.val;
    }
    return dfs(node.left, remaining - node.val)
        || dfs(node.right, remaining - node.val);
  }
  return dfs(root, target);
}

Common mistakes

• Treating a single null child as a leaf, which is wrong for path-sum problems — a leaf has BOTH children null.
• Validating a BST by checking only the immediate child instead of carrying down a min/max range; this misses cross-subtree violations.
• Forgetting to remove a node from the running path when backtracking in path-collection problems, which produces stale paths.
• Returning early from `dfs` before visiting both subtrees when the problem requires aggregating both results.
• Using global mutable state for the answer instead of returning values up the call stack, which breaks when the function recurses on multiple inputs.