Depth-First Search I

Depth-first search follows one path as far as it goes before backing up. On a binary tree it is plain recursion: every node has exactly one path from the root, so nothing is ever reached twice and no visited mark is needed.

The return value is what makes it useful. Each call finishes its children before it finishes itself, so a subtree's answer is ready on the way back up: a depth, a height, a sum. When the thing you want is not the thing you return, keep it in a variable outside the recursion and update it at every node while the return value carries something else upward.

Recursion depth is the limit. A tree of $n$ nodes can be a single chain $n$ deep, so a very deep tree can overflow the default call stack and needs an explicit stack instead.

The problems below start with a value that flows straight up from the children, move to a post-order that returns one thing while a global accumulates another, and end with a descent that records structure to use after it finishes.