AlgoViz
HomeDepth-First Search

Return Values

Medium

Let each call hand a fact upward

Problem

Learn to return information up a DFS (heights, sums, booleans) so a parent can combine child results.

In simple words

Each call hands its answer back up so the parent can combine them.

The idea

Many tree problems ask for something at every node — a height, a subtree sum, a validity flag. Returning that value from the recursion means one pass computes it everywhere, instead of recomputing per node and paying O(n²).

The trick

  • Design the return value first; the rest of the function usually follows.
  • Bundle several facts into a small struct when one is not enough.
  • Returning a sentinel like -1 can signal failure without a second traversal.
123456

Step 1 of 8. A node's height is 1 + the taller of its two subtrees. Solve leaves first, then bubble up.

1/8
Optimal
timeO(n)spaceO(h)

Post-order combine.

1function depth(node) {2  if (!node) return 0;3  return 1 + Math.max(depth(node.left), depth(node.right));4}

Input

nodes
6, 5 edges

Output

max depth
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
height via dfs
Output:
1+max(childHeights)

Finished the walkthrough? Add it to your streak.