Depth-First Search I

Depth-first search follows one branch as deep as it goes before backing up. On a binary tree it is plain recursion, and since every node has one path from the root, no visited set is needed.

Pattern	What the recursive call does	Typical use
Pure bottom-up	Returns a value computed from its children	Maximum depth, subtree sum
Return vs. track	Returns one branch upward, updates a separate best	Tree diameter
Record on descent	Stores parent or depth as it walks	Node-to-node distances

The return value does the heavy lifting. A call finishes both children before itself, so each subtree's result is ready on the way back up. When the answer differs from what a parent needs, say the longest path through a node uses both children but its parent can extend only one, keep the best in an outside variable and return the one-branch value.

Approach	Time	Call-stack space
Recompute each subtree from every node	$O(n^2)$	$O(h)$
One post-order pass, balanced tree	$O(n)$	$O(\log n)$
One post-order pass, skewed tree	$O(n)$	$O(n)$

Use it when a node's answer depends on its subtrees' answers, or to record ancestry and depth in one pass.

The problems below start with maximum depth flowing up from the children, move to tree diameter where the return value and the answer differ, and end with recording depths and parents to measure the distance between two nodes.