Command Palette

Search for a command to run...

← All patterns

Pattern · Trees

Tree DFS

Recurse into the left and right children and combine what they return (height, sums, paths).

Time O(n) · Space O(h) where h is the tree height

Taught in Module 16: Binary Trees

Think of it like this

Asking every manager in a company "how many people report to you?": each asks their direct reports first, then adds them up.

Clues that point here

  • → Binary tree input
  • → Height, depth, diameter, path sums
  • → "Same tree", "symmetric", "invert"
  • → Answer depends on both subtrees

Not this pattern when

  • ✕ The question is about levels or the shortest distance from the root (BFS)

The template

A skeleton to adapt. The parts in comments are what changes from problem to problem.

Tree DFS · template
int dfs(TreeNode node) {
    if (node == null) return 0;          // base case
    int left = dfs(node.left);
    int right = dfs(node.right);
    return combine(node.val, left, right);   // e.g. 1 + Math.max(left, right)
}

Common versions

  • Maximum depth
  • Diameter
  • Path sum
  • Invert tree
  • Lowest common ancestor
  • Balanced tree check

Practice problems with this pattern

Related patterns