Binary Tree DFS — Invert, Max Depth, Diameter, and Subtree Matching

DFS on binary trees runs on a single idea: recurse to the leaves, then build your answer on the way back up. The base case handles null nodes. The recursive case combines results from both children. Most tree problems are solved entirely within this structure.

What trips people up is the return value. What does each recursive call return, and how do you combine left and right results at the current node? Get that right and the code almost writes itself.

This article covers four problems that illustrate the main DFS patterns: mirroring a tree, measuring depth, finding the diameter, and matching a subtree. They go from "warm-up" to "global state during recursion," which is the trickiest move in tree DFS.

The DFS Return-Value Pattern

Every tree DFS follows this structure:

const dfs = (node) => {
  if (!node) return BASE_CASE;      // null node — define what 0/null/false means
  const left = dfs(node.left);      // recurse left
  const right = dfs(node.right);    // recurse right
  // combine left, right, and node.val to produce the return value
  return COMBINED_RESULT;
};

The hard part is choosing what BASE_CASE and COMBINED_RESULT should be. For depth problems, base is 0 and combined is 1 + max(left, right). For sum problems, base is 0 and combined is left + right + node.val. Each problem has its own shape.

Visualizing DFS Post-Order

Problem 1: Invert Binary Tree (LC 226)

Swap every node's left and right child, recursively. The tree [4,2,7,1,3,6,9] becomes [4,7,2,9,6,3,1].

Brute Force: BFS with Queue

Level-order traversal, swapping children at each node.

// Input: root = [4,2,7,1,3,6,9]
// Output: [4,7,2,9,6,3,1]
 
const invertTreeBFS = (root) => {
  if (!root) return null;
 
  const queue = [root];
 
  while (queue.length) {
    const node = queue.shift();
 
    // Swap left and right
    [node.left, node.right] = [node.right, node.left];
 
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
 
  return root;
};
// Time: O(n) node visits, but O(n²) as written — `queue.shift()` re-indexes the whole
//       array, so a wide tree pays for it. Swap in a head pointer or a two-array
//       swap to get a true O(n).
// Space: O(w) — queue holds at most the widest level

This works but requires extra space for the queue. It also pays for queue.shift(): on a perfect tree of 131,071 nodes the shift version takes ~735ms versus ~7ms for a two-array swap on the same machine, because each shift moves every remaining element. Fine on interview-sized inputs, not something to ship.

Optimized: Recursive DFS

Post-order: recurse on both subtrees, then swap at the current node.

// Input: root = [4,2,7,1,3,6,9]
// Output: [4,7,2,9,6,3,1]
 
const invertTree = (root) => {
  if (!root) return null;
 
  // Invert subtrees first
  const left = invertTree(root.left);
  const right = invertTree(root.right);
 
  // Swap at current node
  root.left = right;
  root.right = left;
 
  return root;
};
// Time: O(n) — visits every node once
// Space: O(h) — call stack depth equals tree height (O(log n) balanced, O(n) skewed)

You could also swap before recursing (pre-order) — it produces the same result here because every node gets swapped either way. Post-order is the cleaner mental model for "build answer from children up."

Problem 2: Maximum Depth of Binary Tree (LC 104)

Return the number of nodes along the longest root-to-leaf path.

Brute Force: Iterative DFS with Stack

Push (node, depth) pairs onto a stack, track the running maximum.

// Input: root = [3,9,20,null,null,15,7]
// Output: 3
 
const maxDepthIterative = (root) => {
  if (!root) return 0;
 
  const stack = [[root, 1]];
  let maxD = 0;
 
  while (stack.length) {
    const [node, depth] = stack.pop();
    maxD = Math.max(maxD, depth);
 
    if (node.left) stack.push([node.left, depth + 1]);
    if (node.right) stack.push([node.right, depth + 1]);
  }
 
  return maxD;
};
// Time: O(n) | Space: O(n) — stack can hold all nodes in worst case

Optimized: Recursive DFS

The recursion itself encodes the depth. The return value is the height of the subtree rooted at the current node.

// Input: root = [3,9,20,null,null,15,7]
// Output: 3
 
const maxDepth = (root) => {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};
// Time: O(n) | Space: O(h) — call stack depth

This is the cleanest form. Base case: null is depth 0. Recursive case: depth is 1 (this node) plus the maximum of left and right subtree depths. Four lines, O(h) space instead of O(n).

Problem 3: Diameter of Binary Tree (LC 543)

The diameter is the length of the longest path between any two nodes (measured in number of edges, not nodes). The path doesn't have to go through the root.

This is where the "global state during recursion" pattern appears. The diameter through any node is left_height + right_height — the longest path down left plus the longest path down right. But you can't return this from DFS because your parent also needs the height to compute its own potential diameter. You need to return one value (height) while also tracking another (diameter).

Brute Force: O(n²) — Recompute Heights at Each Node

For each node, compute the height of its left and right subtrees separately, then sum them. This recalculates heights redundantly.

// Input: root = [1,2,3,4,5]
// Output: 3
 
const height = (node) => {
  if (!node) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
};
 
const diameterOfBinaryTreeBrute = (root) => {
  if (!root) return 0;
 
  // Diameter through this node
  const throughRoot = height(root.left) + height(root.right);
 
  // Diameter might be entirely in left or right subtree
  const leftDiameter = diameterOfBinaryTreeBrute(root.left);
  const rightDiameter = diameterOfBinaryTreeBrute(root.right);
 
  return Math.max(throughRoot, leftDiameter, rightDiameter);
};
// Time: O(n²) — height is O(n), called at each of n nodes
// Space: O(h)

This O(n²) approach is correct but slow. For a balanced tree it's O(n log n); for a linear tree it degrades to O(n²).

Optimized: Single DFS, Track Global Max

Compute height and update the diameter simultaneously in one pass. The DFS function returns height (for the parent's calculation) while updating an outer maxDiameter variable as a side effect.

// Input: root = [1,2,3,4,5]
// Output: 3
 
const diameterOfBinaryTree = (root) => {
  let maxDiameter = 0;
 
  const dfs = (node) => {
    if (!node) return 0;
 
    const leftHeight = dfs(node.left);
    const rightHeight = dfs(node.right);
 
    // The diameter through this node: sum of both sides
    maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
 
    // Return height for the parent's diameter calculation
    return 1 + Math.max(leftHeight, rightHeight);
  };
 
  dfs(root);
  return maxDiameter;
};
// Time: O(n) — single post-order traversal
// Space: O(h) — call stack

The outer variable maxDiameter is the key move. The inner dfs returns height (what the parent needs), but also updates the global max as a side effect (what you ultimately need). These are two different concerns collapsed into one pass.

Problem 4: Subtree of Another Tree (LC 572)

Given trees root and subRoot, return true if subRoot is a subtree of root — meaning some node in root has a subtree identical in structure and values to subRoot.

This problem stacks two DFS concerns: one traversal to find candidates, another to verify matches.

Solution: Nested DFS

Separate the "find a matching starting node" logic from the "verify exact match" logic. Two functions, each simple.

// Input: root = [3,4,5,1,2], subRoot = [4,1,2]
// Output: true
 
const isSubtree = (root, subRoot) => {
  // isSameTree: structural equality check
  const isSameTree = (t1, t2) => {
    if (!t1 && !t2) return true;   // both null — same
    if (!t1 || !t2) return false;  // one null, one not — different
    return (
      t1.val === t2.val &&
      isSameTree(t1.left, t2.left) &&
      isSameTree(t1.right, t2.right)
    );
  };
 
  // dfs: find any node in root matching subRoot
  const dfs = (node) => {
    if (!node) return false;
    if (isSameTree(node, subRoot)) return true;
    return dfs(node.left) || dfs(node.right);
  };
 
  return dfs(root);
};
// Time: O(m × n) — for each of m nodes in root, isSameTree may check n nodes
// Space: O(h) — call stack for dfs, plus isSameTree stack on top

The || short-circuits: if the left subtree already contains subRoot, you don't touch the right. This is why dfs returns a boolean and not void.

DFS Pattern Reference

The diameter pattern (return one value, update outer variable) also applies to: Binary Tree Maximum Path Sum (LC 124), Longest Univalue Path (LC 687), and Longest ZigZag Path (LC 1372).

Interview Tips

State the return value before coding. For any tree DFS problem, the first thing to say out loud: "My DFS function returns X." If you can't state it clearly, you don't have the solution yet. For diameter: "My DFS returns height, but I track the diameter separately."

Null node base case is your contract. If you return 0 for null in max-depth, you're saying "a null tree has depth 0." This propagates correctly — a leaf node gets 1 + max(0, 0) = 1. Make sure your base case value is consistent with what "empty" means for your specific calculation.

On isSameTree: Interviewers sometimes give LC 100 (Same Tree) as a warm-up, then immediately ask LC 572 (Subtree). They're testing whether you recognize isSameTree as a reusable building block. Write isSameTree first, then wrap it.

Recognize the diameter pattern by its smell: If a problem asks for a "longest path" or "maximum sum path" through any node, and the answer can't be the return value of your DFS, you need the outer variable pattern.

The O(h) vs O(n) space trade-off: DFS uses O(h) call stack space. For a balanced tree h = O(log n), for a linear tree h = O(n). Your interviewer may ask "what's the worst-case space?" — the answer is O(n) for a degenerate (stick) tree. If they push for a constant-space solution, that requires Morris traversal, which is usually out of scope.