What each subtree reports back

The return value is what the parent needs. The answer can be something else.

Saturday's two problems. In diameter, every call returns a height but checks a path, and the best path is kept on the side. In lowest common ancestor, every call reports what it found, and the answer is the first node to hear back from both sides.

problem
The tree being walked, with what each call has returned

running now waiting on the stack height returned path checked here longest path so far empty subtree (nullptr)

Press Next to make the first call.

Call stack

    LC 543

    Diameter: return one number, keep another

    Every path in a tree has one highest node, where it stops going up and starts going down. A path that turns at node v goes as deep as it can on the left and as deep as it can on the right: lHeight + rHeight edges. Each call checks that one candidate, so all turning points get checked once.

    The parent can't use that path, though: a path can't fork. All the parent can extend is the deepest path going straight down through v, which is the height. So the function returns the height and only records the diameter. Pick the tree where the longest path skips the root: the answer is found under node 2 and never changes after that.

    The return value is what the parent needs. The answer is kept on the side.

    LCA: report what you found

    Every call reports one of three things: nothing (nullptr), the one target it found, or the answer. A node that finds p or q returns it at once without looking below, so its subtree stays grey. The first node to hear back from both sides returns itself, and every node above it just passes that up.

    Pick p = 5 and q = 4: the walk stops at 5 and never sees 4, yet the answer is right. Either 4 is below 5, which makes 5 the LCA, or it's somewhere else, and then some ancestor hears from both sides. LeetCode guarantees both nodes are in the tree, which is what makes the shortcut safe.