Trace -10(9, 20(15, 7)).
Process 15 (leaf): gain = 15. Max path through 15 = 15. Global max = 15.
Process 7 (leaf): gain = 7. Max path through 7 = 7. Global max = 15.
Process 20: leftGain = 15, rightGain = 7.
- Path through 20:
15 + 20 + 7 = 42. Global max = 42. - Gain to parent:
20 + max(15, 7) = 35.
Process 9 (leaf): gain = 9. Max path = 9. Global max = 42.
Process -10: leftGain = 9, rightGain = 35.
- Path through -10:
9 + (-10) + 35 = 34. Global max still 42. - Gain to parent:
-10 + 35 = 25.
Return 42.
Visit each node once. time. Recursion stack: space.