Binary Tree Maximum Path Sum
The problem
Find the largest sum along any nonempty path in a binary tree. A path follows parent-child edges without revisiting a node; it need not include the root.
Example
Root −4 with children 6 and 8 → 10, along 6 → −4 → 8
Need a hint?
A path returned to a parent can use only one downward branch.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
At each node, compute the best nonnegative gain from each child. Update a global answer with node value plus both gains. Return node value plus the larger gain to the parent. Initialize the answer below every value so an all-negative tree still chooses a node.
Complexity
O(n) time and O(h) stack space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.