Tree contributions and search order

Opening your lesson

A recursive tree function often answers a smaller question than the final problem asks. A subtree height is a downward arm that a parent can extend. A maximum path can join two arms at their shared parent, but that joined shape can't itself be returned as one arm. Keep those two meanings separate.

You will begin by summing only leaves, then read a right-side view by breadth-first levels and find a ranked key by inorder traversal. The final tasks count downward target sums and maximize a signed route. For the path-count map, record only ancestors on the active branch and undo each addition when returning. These trees have a depth bound of 300; without such a bound, an iterative traversal avoids depending on the language call-stack limit.

tree = [1, 2, 3]
leaf contributions: 2 and 3
height of each child: 1
longest route through root: 1 + 1 = 2 edges
maximum signed route: 2 + 1 + 3 = 6
arm returned from root: 1 + max(2, 3) = 4

The root can join both child arms when evaluating a complete route. For the signed values shown, that route totals six. Its parent, if one existed, could extend only one side without visiting the root twice, so the root returns four as its best downward arm. A height calculation makes the same distinction using node counts instead of gains: each child height is one, and joining them gives two edges through the root. The leaf-balance task uses another return meaning entirely, summing two and three while excluding the internal root value. Name the return value before writing the recurrence.

Choose your character

Your Work Gym account