Tree DFS: Think in Subtrees

Intermediate · 24 min read · Problem-Solving Patterns, Trees

Return values up, pass constraints down — depth, paths, diameter and LCA.

Trees are where recursion stops being scary and starts being the obvious tool — because a tree is recursive. A binary tree is either empty, or a node with a left subtree and a right subtree.

The core move: trust the children

Answer three questions, exactly as in Recursion Without Fear:

Direction 1: return values up (bottom-up)

The node needs facts about its subtrees. Each call returns a summary to its parent.

Direction 2: pass context down (top-down)

The node needs facts about its ancestors. Pass them as parameters.

Direction 3: return one thing, record another

The trickiest tree problems involve paths that bend at a node — they go up from the left subtree, through the node, and down into the right subtree. Such a path can't be extended to the parent (a path can't fork). So each call does two things:

Lowest common ancestor

Each call returns "p, q, or their LCA if found in this subtree, else null". If p and q turn up on different sides, this node is where their paths meet:

Building and serialising trees

Preorder lists the root first; inorder lists the left subtree, then the root, then the right subtree. So: take the next preorder value as the root, find it in inorder to split the range, recurse.

Which direction?

Practice ladder

Interview questions

  • In the diameter problem, why does the function return one side but record both?
  • What's the time and space complexity of a recursive DFS on a binary tree?

Further reading

Key takeaways

  • Tree DFS = empty case + trust the children + combine at the node.
  • Facts about subtrees flow up (return values); facts about ancestors flow down (parameters).
  • For paths that bend at a node: record the bent path globally, return only one side.
  • Return sentinels (like −1) to avoid recomputing; clamp negative branches to 0 in path sums.
  • Root-to-leaf means stop at leaves, not nulls.

Previous: Heaps: Top-K, K-Way Merge, Two Heaps · Next: Tree BFS: Level by Level