menu_bookGyanByte
Lesson 133 min read

Tree DFS (Recurse, Combine, Return)

November 05, 2026

// TL;DR

Depth-first search recurses down one branch fully before backtracking — naturally expressed with recursion (the call stack IS your stack). Almost every tree DFS follows one shape: handle the empty/base case, recurse LEFT, recurse RIGHT, then COMBINE the results with the current node. Max depth = max(left, right) + 1; path sum subtracts and checks a leaf; diameter tracks the best left+right; validate-BST passes down min/max bounds; LCA bubbles up where the two targets are found. Signals: 'path', 'depth/height', 'subtree', 'ancestor', 'is it a valid BST'. O(n) time, O(h) space (recursion stack, h = tree height). Learn the shape and most tree questions become fill-in-the-blank.

If BFS is for levels, DFS is for paths and subtrees — and almost every tree DFS problem is the same three-line shape. Learn it once and a dozen questions become trivial.

The idea

Tree DFS, recurse, combine, return. A tree root 1 with children 2 and 3, and 2's children 4 and 5. The recursive shape: def dfs(node): if not node return base; L equals dfs of node.left; R equals dfs of node.right; return combine of node.val, L, R. Examples: depth is max of L and R plus 1; sum is L plus R plus val. The idea: depth-first search recurses down one branch fully before backtracking, naturally expressed with recursion, the call stack is your stack; almost every tree DFS handles the empty base case, recurses left, recurses right, then combines the results with the current node; max depth combines with max plus 1, path sum subtracts and checks a leaf, diameter tracks the best left plus right. Use it for max depth, path sum, diameter, lowest common ancestor, validate BST, invert tree, serialize.

DFS goes deep down one branch before backtracking, which recursion expresses perfectly (the call stack is the stack). The universal shape:

def dfs(node):
    if not node:
        return <base value>        # empty subtree
    L = dfs(node.left)             # solve the left subtree
    R = dfs(node.right)            # solve the right subtree
    return combine(node.val, L, R) # build this node's answer from the children

You only ever change two things: the base value and the combine step. O(n) time (each node once), O(h) space (recursion depth = tree height).

Four worked examples (same shape)

Max depth — combine is max(L, R) + 1:

def max_depth(root):
    if not root: return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Path sum (root-to-leaf summing to a target) — subtract as you go, check at a leaf:

def has_path_sum(root, target):
    if not root: return False
    if not root.left and not root.right:      # leaf
        return target == root.val
    rem = target - root.val
    return has_path_sum(root.left, rem) or has_path_sum(root.right, rem)

Diameter (longest path between any two nodes) — a common trick: the recursion returns the height, but a side variable tracks the best left + right seen:

def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if not node: return 0
        L = height(node.left); R = height(node.right)
        best = max(best, L + R)        # path through this node
        return 1 + max(L, R)           # height to return upward
    height(root)
    return best
# diameter of (1 / (2/(4,5)), 3) -> 3

Validate BST — pass bounds down so each node knows its allowed range:

def is_valid_bst(root, lo=float("-inf"), hi=float("inf")):
    if not root: return True
    if not (lo < root.val < hi): return False
    return (is_valid_bst(root.left,  lo, root.val) and
            is_valid_bst(root.right, root.val, hi))

Notice the two flavours: some problems combine results coming up (depth, diameter, sum), others pass constraints down (validate-BST bounds). Many do both. Lowest-common-ancestor bubbles up “where did I find the targets?“.

Step-by-step walkthrough

Trace Maximum Depth on the same tree (3 → (9, 20), 20 → (15, 7)). DFS goes all the way down first; each node returns only after both children have reported (post-order), so the answers bubble up from the leaves.

node returns left depth right depth computation
9 0 0 1 + max(0, 0) = 1
15 0 0 1 + max(0, 0) = 1
7 0 0 1 + max(0, 0) = 1
20 1 1 1 + max(1, 1) = 2
3 1 2 1 + max(1, 2) = 3

Read top to bottom, this is the order the calls finish: leaves first, root last. The root returns 3. The same recurse–combine–return shape solves diameter, path sums, and balanced-tree checks.

When to reach for it

Signals: the answer is about a path (root-to-leaf, node-to-node), a subtree property (height, balanced, count), an ancestor relationship (LCA), or a structural check (is it a valid BST, are two trees the same, invert/mirror). Anything recursive on a tree where “the answer here depends on the answers below” is DFS.

Pitfalls

  • Missing the base case. Always handle None first, or you’ll dereference null.
  • Confusing “return up” with “pass down”. Decide whether information flows up (combine children) or down (constraints like BST bounds) — mixing them is a classic bug (diameter needs the side variable precisely because the return value and the answer differ).
  • Deep recursion. Very deep/skewed trees can hit recursion limits; mention an iterative stack version if asked.

Recap

Tree DFS is recursion with one shape: base case → recurse left → recurse right → combine. Change only the base value and the combine step and you get max-depth, path-sum, diameter, validate-BST and LCA. Information flows up (combine children) or down (pass constraints) — know which your problem needs. O(n) time, O(h) space. Reach for DFS on paths, subtrees and structure; BFS on levels.

Practice: 13 solved problems on tree DFS → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 14 — Heaps / Top-K.

exercisePractice this patternTree DFS — Practice Problemsarrow_forward
coding-interviewtreedfsrecursionpython
arrow_back PreviousTree BFS (Level-Order Traversal)Next arrow_forwardHeaps / Top-K / Two Heaps