Tree DFS

TL;DR

Tree DFS is recursion with one rule: at every node, decide whether you do work before recursing (pre-order), between recursing left and right (in-order), or after both children return (post-order). Pick the order that matches when your answer is ready.

Pre-order (root, left, right) is the natural fit for top-down work — copy a tree, serialise it, print an outline, push state from parent to child. In-order (left, root, right) on a BST visits values in sorted order, which is why “kth smallest in BST” and “validate BST” both reduce to a one-line in-order check. Post-order (left, right, root) is the workhorse: anything where the parent’s answer is a function of its children’s answers — depth, diameter, balanced, max path sum, “delete leaves matching X” — folds bottom-up.

The other axis is direction of information flow. Bottom-up DFS returns a value from each call and the parent combines them. Top-down DFS passes state down as an argument (remaining target, current path, accumulated sum) and the leaf decides. Most non-trivial tree problems are one of these two shapes wearing different clothes.

When to reach for it

Reach for tree DFS when:

• The answer at a node is a function of its subtree results — depth, diameter, height-balanced, sum of all paths, count of nodes matching a predicate.
• You need to traverse every node exactly once and the order matters (serialise, clone, print).
• A problem says “BST” and asks for sorted/ranked output — in-order DFS is the move.
• You’re carrying state from root to leaf — path sums, ancestor lists, remaining budget.

Reach for BFS instead when the question is about levels (level order, zigzag, right-side view, shortest path in an unweighted graph). Reach for iterative DFS with an explicit stack when recursion depth is a real risk (see pitfalls).

Flavor 1 — pre/in/post-order traversal

The three orders are the same recursion with the visit line moved.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(node, out):
    if node is None: return
    out.append(node.val)        # visit
    preorder(node.left, out)
    preorder(node.right, out)

def inorder(node, out):
    if node is None: return
    inorder(node.left, out)
    out.append(node.val)        # visit
    inorder(node.right, out)

def postorder(node, out):
    if node is None: return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)        # visit

Worked example. Run all three on this tree:

        1
       / \
      2   3
     / \   \
    4   5   6

Stepping through pre-order: visit 1, recurse left into 2, visit 2, recurse left into 4, visit 4 (leaf), back up, recurse right into 5, visit 5, back up to 1, recurse right into 3, visit 3, recurse right into 6, visit 6.

If this tree were a BST you’d want in-order to give sorted output. It isn’t (2’s right child 5 < parent 1 fails BST), so the in-order sequence here is just the structural left/root/right walk — useful for printing, not for sort.

Flavor 2 — bottom-up DFS (post-order folds)

The pattern: each call returns one value computed from its children’s return values. The parent folds them. The recursion is the post-order traversal.

def helper(node):
    if node is None:
        return base_case          # 0 for depth, -inf for max, etc.
    left = helper(node.left)
    right = helper(node.right)
    return combine(node, left, right)

Worked example: diameter of binary tree (LC 543). The diameter is the longest path (in edges) between any two nodes. Key observation: the longest path that passes through a node v has length left_depth(v) + right_depth(v). The answer is the max of that quantity over all nodes. Each call returns the depth of the subtree (so the parent can use it) while updating a global best.

def diameter_of_binary_tree(root):
    best = 0
    def depth(node):
        nonlocal best
        if node is None:
            return 0
        l = depth(node.left)
        r = depth(node.right)
        best = max(best, l + r)   # path through node, in edges
        return 1 + max(l, r)      # depth contributed to parent
    depth(root)
    return best

Trace on the tree above. Depth returned is 1 + max(l, r); l + r is the candidate diameter through that node.

Answer: 4 edges (the path 4 → 2 → 1 → 3 → 6). The fold runs in post-order because node 1 can’t compute l + r until both children have returned their depths.

The same skeleton solves max depth (return 1 + max(l, r), no global), balanced-binary-tree (return -1 to short-circuit when an imbalance is found), and binary-tree-max-path-sum (LC 124) — change only the combine.

Flavor 3 — top-down DFS (passing state down)

When the answer depends on the path from the root rather than the subtree, push state down as an argument.

def helper(node, state):
    if node is None:
        return False
    new_state = update(state, node)
    if is_leaf(node):
        return check(new_state)
    return helper(node.left, new_state) or helper(node.right, new_state)

Example: path sum (LC 112). Does any root-to-leaf path sum to target? Carry the remaining target down; at a leaf, check if it hit zero.

def has_path_sum(root, target):
    if root is None:
        return False
    remaining = target - root.val
    if root.left is None and root.right is None:
        return remaining == 0
    return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)

On the tree above with target = 7: at 1, remaining = 6. Down to 2, remaining = 4. Down to 4 (leaf), remaining = 0 → True. The state (remaining) flowed root → leaf; nothing came back up beyond the boolean.

Top-down also covers: collecting all root-to-leaf paths (carry a list, copy on push), counting good nodes (carry max-on-path), and lowest-common-ancestor variants that thread depth or ancestry down.

Why it works — the invariant

Every recursive DFS is using the call stack as an implicit stack of unfinished work. When you call dfs(node.left), the frame for node is suspended with its local variables intact (including node, the unread node.right, and any partial results). When the left subtree finishes, the frame resumes exactly where it left off. That’s why post-order can fold results — the parent’s frame is still alive, holding the slot where left and right will land.

Each node is pushed onto the call stack exactly once and popped exactly once. That’s the visit-each-node-once guarantee.

Complexity

• Time: O(n). Constant work at each node, n nodes.
• Space: O(h), where h is the tree height — the maximum depth of the call stack. Balanced tree → O(log n). Skewed tree (linked-list-shaped) → O(n). The recursion stack dominates; if you also build an output list, add O(n) for that.

Common pitfalls

• Skewed trees blow the recursion limit. Python’s default is 1000. A 10,000-node left-skewed tree (LC test cases love these) crashes with RecursionError. Either bump it (sys.setrecursionlimit(10**6)) or rewrite iteratively with an explicit stack = [root] loop. The iterative rewrite is unavoidable for production code where recursion depth isn’t bounded.
• Forgetting the None base case. if node is None: return is the single most common omission. Without it, you’ll dereference .left on None and crash. Write the base case first, before the recursive calls.
• Mutating shared state across siblings. If you carry a list down by reference (e.g. for collecting paths), append before recursing and pop after — otherwise the right subtree sees the left subtree’s appended values. The fix is either pop-after-recurse (backtracking) or pass an immutable copy path + [node.val] down.
• Helper that should fold a value but returns nothing. A bottom-up helper must return from every branch — including the None base case. A missing return turns into an implicit None and the parent’s combine(left, right) crashes on arithmetic with None.
• Confusing pre-order and post-order semantics. Pre-order can’t see children’s results yet; post-order can’t see ancestors’ state unless you threaded it down. Pick the order based on when your answer is ready, not by habit.

Where you see this in production

• Compiler AST traversal — Clang’s RecursiveASTVisitor. Every C++ static analyser, linter, and refactoring tool walks the AST with a pre-order DFS, with VisitFoo(FooDecl*) hooks at each node type. Same shape as preorder above, just with virtual dispatch.
• React’s fiber tree reconciler. React walks its component tree depth-first, completing children before their parent (post-order) so the parent can see committed child output before deciding its own DOM mutations. Reconciliation is literally a bottom-up fold.
• du and find in Unix. du is post-order — a directory’s size is the sum of its children’s sizes, computed only after the children are done. find is pre-order by default — print the directory, then recurse into it.
• Babel and other JS transpilers. Babel’s @babel/traverse walks the ESTree AST with both enter (pre-order) and exit (post-order) hooks per node, so plugins can either rewrite tokens on the way down or rebuild nodes from transformed children on the way up. BeautifulSoup’s descendants iterator does the same for HTML.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.