Recursion and Trees
Return one thing, update another
The most important idea in the unit. What a node reports to its parent is not always what the answer is.
Key idea
Where the confusion comes from
Consider measuring the longest path between any two nodes. Such a path might not pass through the root at all; it could sit entirely inside the left subtree.
So the recursion has to compute two different things. The answer, which is the best path found anywhere so far, and the thing a node can usefully tell its parent, which is how far down it extends.
Those are not the same quantity, and trying to return one number for both is why this family of problems feels impossible before the idea lands.
Why it works
The two quantities, named
What a node returns is the best value of something that continues upward: a path going down one side only, since a parent can only extend a path through one of its children.
What a node updates is a running best that considers the case where this node is the topmost point of the answer, which may combine both children.
Write those two sentences before writing the function. Every problem of this shape is the same two sentences with different quantities in them.
Here are the mechanics on a deliberately boring pair of quantities, so that only the structure is on show. The depth travels upward as a return value. The count of nodes with two children never travels anywhere; it is recorded where it is found.
Tip
`nonlocal` versus a mutable holder
nonlocal forks lets the inner function assign to a name defined in the enclosing function. Without it, assigning creates a new local and the outer name never changes, which is a silent failure that returns the initial value.
An alternative is to hold the value in a one-element list and mutate it, which works because mutation is not assignment. Both are common; nonlocal says what you mean more clearly.
Gotcha
Count edges or count nodes, and be consistent
When the updated quantity measures a path, left + right counts edges if the base case returns 0 for an empty child. If the base case returned 1 for a leaf instead, the same expression would double count the node in the middle.
Decide up front whether your recursion is measuring in edges or nodes, then check both the base case and the combination against that decision. Answers that are off by exactly one throughout are almost always this.
Gotcha
The answer may never pass through the root
The quantity a node updates has to be checked at every node, not just at the root, because the best answer can sit entirely inside one subtree and never touch the top of the tree.
The straight chain above is the shape that makes this visible. Its depth climbs to 4 while its fork count never leaves 0, so the two quantities move on entirely separate schedules and neither can be read off the other. Cases where the answer lies wholly on one side, or never appears at the root at all, are exactly the ones a return-only solution gets wrong, which is why they are worth testing first.
Key idea
A variation you will meet later
Some problems in this family allow a child's contribution to be rejected, for instance when values can be negative and a subtree would only make things worse.
The fix is one function call: clamp the child's contribution at zero before using it. The two-quantity structure is unchanged. When you meet the hardest problem in this unit, that clamp plus these two sentences is the entire solution.
Trace the two quantities
Run deepest_and_forks on the tree T(1, T(2, T(4), T(5)), T(3)). For each node give what depth returns and what forks holds immediately after that node has been handled. Nodes are visited in postorder: 4, 5, 2, 3, 1.
This activity type is not wired up yet.
Diameter Of Binary Tree
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.