Max Path Sum From Leaf To Root

Given a binary tree in which each node contains an integer number. Find the maximum possible path sum from a leaf to root.

Assumptions

The root of given binary tree is not null.

Examples

10

/ \

-2 7

/ \

8 -4

The maximum path sum is 10 + 7 = 17.

Solution: Recursive bottom up

Base Case: root == null, return 0

From Children: get two max value paths

At current level:

To parent: pick higher value path between left and right and return to parent