← All patterns

Tree DFS

Recursive depth-first traversal. Pre / in / post-order, path-sum aggregation, LCA, height, diameter, serialization, BST validation — most tree questions reduce to a single DFS with carefully chosen return values.

21 problems 7 Easy 9 Medium 5 Hard

Recursive depth-first traversal of binary trees. The strategic question is always: what does each recursive call *return*? Often a tuple (height + best-path, rob + skip, count + sum) so the parent can combine without re-DFSing.

Pre/in/post-order each have a natural fit: in-order for BSTs (yields sorted), post-order for bottom-up aggregations (height, diameter), pre-order for path reconstruction.

When to reach for this pattern

  • Binary tree input with no parent pointer
  • Per-node computation depending on subtree information
  • Path-based questions (path sum, longest path, diameter)
  • Tree validation (BST, balanced, symmetric)

Canonical template 

// post-order combine pattern
int dfs(TreeNode* n) {
    if (!n) return 0;
    int l = dfs(n->left), r = dfs(n->right);
    // combine l, r, and n->val into this node's contribution
    return ...;
}

// tuple-return for two-state DP per node
pair<int, int> dfs(TreeNode* n) {
    if (!n) return {0, 0};
    auto [lRob, lSkip] = dfs(n->left);
    auto [rRob, rSkip] = dfs(n->right);
    int rob  = n->val + lSkip + rSkip;
    int skip = max(lRob, lSkip) + max(rRob, rSkip);
    return {rob, skip};
}

C++ · adapt the names and types to your problem.

Common pitfalls

  • Forgetting to handle the null-node base case
  • Updating a 'best' global from inside DFS but returning a *different* quantity — easy to mix up
  • BST validation: compare against an ancestor range, not just the direct parent
  • Recursion depth on skewed trees can hit stack limits; iterative DFS via explicit stack avoids it

Related patterns

Tree BFS Backtracking Dynamic Programming

Problems (21)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.