Tree Depth-First Search

How It Works

Depth-first search on a tree means fully exploring one branch, going as deep as possible, before backtracking and exploring the next. For binary trees, this almost always takes the shape of a recursive function: solve the problem for a node by combining the answers from its left and right subtrees, with a base case for null (an empty subtree).

Three traversal orders fall naturally out of where you "visit" the current node relative to recursing into its children: preorder (visit node, then left, then right), inorder (left, then node, then right; produces sorted output for a valid BST), and postorder (left, then right, then node; useful when a node's answer depends on both children's answers, like height or diameter).

Most "tree" interview questions are DFS in disguise: computing depth, summing root-to-leaf paths, validating BST ordering, or finding the lowest common ancestor of two nodes. The recursive call stack itself acts as the "path so far," which is what makes path-based problems (Path Sum, Binary Tree Paths) so natural to express with DFS: no explicit stack management required, since the call stack does it for you.

When To Use It

• The input is a binary (or n-ary) tree, not a flat array or linked list.
• You need to enumerate or evaluate every root-to-leaf path.
• The problem asks for a tree-wide property computed bottom-up: depth, diameter, balance, sum, or symmetry.
• You need to validate an ordering invariant across the whole tree (e.g., binary search tree property).
• The problem has a clean recursive definition: "the answer for this node depends on the answer for its children."

Time & Space Complexity

• Time: O(n): each node is visited exactly once.
• Space: O(h) for the recursion call stack, where h is the tree's height: O(log n) for a balanced tree, O(n) in the worst case (a completely skewed tree).

// Canonical tree DFS template (node shape: { val, left, right })
function dfs(node) {
  if (node === null) return /* base case value, e.g. 0 */;

  const leftResult = dfs(node.left);
  const rightResult = dfs(node.right);

  // Combine leftResult, rightResult, and node.val into this node's answer.
  return 1 + Math.max(leftResult, rightResult); // example: max depth
}

Alternative Approaches

• Breadth-first search (level-order traversal): better suited for "shortest path" or level-by-level problems (e.g., level averages, right-side view); uses an explicit queue and O(n) space in the worst case rather than O(h).
• Iterative DFS with an explicit stack: avoids recursion-depth limits on very deep/unbalanced trees and is sometimes required when the interviewer explicitly asks for a non-recursive solution.
• Morris Traversal: an O(1)-extra-space inorder traversal that temporarily rewires right pointers instead of using recursion or a stack; niche, but worth mentioning if space is tightly constrained.

Common Mistakes

• Forgetting the null base case: every recursive tree function needs an explicit answer for an empty subtree, or you'll throw trying to read .val off null.
• Confusing "leaf" with "node with at least one null child": a leaf has both children null; a node with only one null child is not a leaf, and treating it as one breaks path-sum-style problems.
• Validating a BST by only checking node.left.val < node.val < node.right.val: this only checks immediate children, not the full-subtree bound; a node deep in the left subtree could still violate the BST property against an ancestor further up.
• Mixing up traversal orders: using preorder when the problem needs sorted (inorder) output, or needing postorder because a node's computation depends on results from both children first.
• Recomputing subtree results redundantly: for problems like diameter, naively calling a separate depth() function inside the main recursion turns O(n) into O(n²); compute depth and the target answer in the same pass instead.

Pattern Summary

Tree DFS is the default lens for binary tree problems: recurse into left and right, combine their results, and let the call stack manage the "current path" for you. The main decisions are which traversal order fits the problem and whether the answer is naturally top-down (pass state into children) or bottom-up (combine results coming back from children).