LESSON 15 · PATTERN GUIDE

Tree DFS

Explore a tree recursively or with a stack, combining information from child subtrees.

FIRST, LEARN THE PATTERNDepth-first search follows a path before returning. A recursive function can return a summary from each subtree to its parent.

The task asks about a root-to-leaf path, subtree property, height, diameter, or a recursive tree transformation.

How to approach it

Define precisely what each recursive call returns and handle the null node as the base case.

Watch out for

A recursive solution may use O(height) call stack and can overflow for a highly skewed tree in some runtimes.

A CLOSER EXPLANATION

A recursive DFS solves a node by asking its children for smaller answers. A helper might return height, a boolean, a sum, or a path result. Clearly defining that return value makes it easier to combine subtrees and handle an empty child.

NOW YOU TRY

Practice question

A binary tree has root 5, children 3 and 8, and node 3 has children 2 and 4. What is its maximum depth?

EXAMPLELevels: [5], [3, 8], [2, 4]Give your answer before revealing the explanation.

Show a hint

Depth at a node is one plus the greater depth of its children.

Show an answer

3 nodes (levels) from root to deepest leaf.

CONNECT IT TO REAL LIFE

Tree DFS at work

A company org chart is a tree. The root manager is at level 1, and the deepest employee is 5 reporting steps below. What is the chart's maximum depth in levels?

Show one possible approach

6 levels: the root level plus 5 edges below it. A DFS can return one plus the larger depth of the manager's child subtrees.

Practice next

Use these problem IDs to find additional practice for this pattern:

104112113543124226