Tree DFS

At a glance

The instinct

A binary tree is a node plus two smaller binary trees. That self-similarity means most tree questions can be phrased as: "if I already knew the answer for my left subtree and my right subtree, how do I produce mine?" Write that rule once, add a base case for null, and the recursion does the walking. The only real design decision is which direction information flows:

• Top-down (pre-order): the parent passes something down - the running sum, the current path, the min/max allowed, the depth.
• Bottom-up (post-order): each child returns a summary - height, subtree sum, "found target?", "is balanced?" - and the parent combines them.

Recognise it

Not this pattern if...

• The question is about levels or "first row where..." - Tree BFS reads more naturally.
• The tree is a BST and you need order statistics or a search - exploit ordering (BST pattern) instead of visiting everything.
• The structure is a general graph with cycles - you need a visited set (graph DFS).

Memory hack

Analogy - a company org chart. The CEO wants total headcount. She does not count everyone; she asks each direct report for their team's count, adds them, adds herself. Each manager does the same. Interns (leaves) answer "1", and empty desks (null) answer "0".

Say it out loud in the interview:

1. "Base case: what do I return for null (and maybe for a leaf)?"
2. "What does each child need to tell me - or what do I need to tell each child?"
3. "How do I combine at this node, and is there a separate global answer for paths that bend here?"

How it works

Bottom-up for Diameter of Binary Tree: height(node) = 1 + max(height(left), height(right)), while the diameter candidate at that node is height(left) + height(right) (edges through the node). The function returns height but updates the diameter.

flowchart TD
  A["dfs(node)"] --> B{"node == null?"}
  B -->|yes| C["return neutral value (0, true, null...)"]
  B -->|no| D["L = dfs(left)"]
  D --> E["R = dfs(right)"]
  E --> F["update global with L + node + R (the bend)"]
  F --> G["return node + best single branch to parent"]

Trace on 1 -> (2, 3), 2 -> (4, 5):

Java template

import java.util.*;

class TreeNode {
    int val; TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class TreeDfs {
    // BOTTOM-UP: return a summary upward, keep the best "bend" in a field.
    private int best = Integer.MIN_VALUE;

    int solve(TreeNode root) {
        best = Integer.MIN_VALUE;
        up(root);
        return best;
    }

    private int up(TreeNode node) {
        if (node == null) return 0;                  // neutral value for an empty subtree
        int l = Math.max(0, up(node.left));          // drop negative branches (max path sum)
        int r = Math.max(0, up(node.right));
        best = Math.max(best, l + node.val + r);     // answer that bends at this node
        return node.val + Math.max(l, r);            // only ONE branch may continue upward
    }

    // TOP-DOWN with backtracking: carry state to children, act at leaves.
    static void down(TreeNode node, int sumSoFar, Deque<Integer> path, List<List<Integer>> out, int target) {
        if (node == null) return;
        sumSoFar += node.val;
        path.addLast(node.val);                      // choose
        if (node.left == null && node.right == null && sumSoFar == target) {
            out.add(new ArrayList<>(path));          // copy - path keeps changing
        }
        down(node.left, sumSoFar, path, out, target);
        down(node.right, sumSoFar, path, out, target);
        path.removeLast();                           // un-choose
    }

    // TWO-TREE lock-step (same tree / symmetric / subtree check).
    static boolean same(TreeNode a, TreeNode b) {
        if (a == null || b == null) return a == b;
        return a.val == b.val && same(a.left, b.left) && same(a.right, b.right);
    }
}

Complexity

• Time: O(n) - each node is visited a constant number of times. Watch out for hidden O(n) work per node (e.g. recomputing height inside a balance check, or indexOf in construction), which makes it O(n^2); precompute or return more from the recursion.
• Space: O(h) recursion stack - O(log n) for balanced trees, O(n) for a skewed one. Very deep inputs can overflow the Java stack; mention an iterative version with an explicit stack.

Variations

• Bottom-up aggregate - height, size, sums. Maximum Depth of Binary Tree, Diameter of Binary Tree, Distribute Coins in Binary Tree.
• Global "bend" answer - return one branch, record both. Binary Tree Maximum Path Sum.
• Top-down state - pass bounds, sums or ancestors' min/max. Maximum Difference Between Node and Ancestor; Path Sum III adds a prefix-sum hash map that is backtracked on the way out.
• Search with reports - children return the node they found. Lowest Common Ancestor of a Binary Tree.
• Two trees together - Same Tree, Symmetric Tree, Subtree of Another Tree.
• Build / reshape - Construct Binary Tree from Preorder and Inorder Traversal (map value to inorder index), Invert Binary Tree, Flatten Binary Tree to Linked List, Delete Nodes And Return Forest.
• Encode subtrees - serialise each subtree to a string or id to spot repeats. Find Duplicate Subtrees, Serialize and Deserialize Binary Tree (pre-order with null markers).

Common mistakes

• Treating a node with one child as a leaf (minimum depth, root-to-leaf sums). A leaf has both children null.
• Forgetting to undo state after recursing (path lists, prefix-sum counts), so siblings see their cousin's data.
• Adding the mutable path itself to the result instead of a copy - every stored path ends up empty.
• Initialising a global max to 0 when all node values may be negative; start at Integer.MIN_VALUE, or seed with the root.
• Using a static field without resetting it between test cases.

All practice problems

22 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.