Maximum Path Sum Binary Tree II

Given a binary tree in which each node contains an integer number. Find the maximum possible sum from any node to any node (the start node and the end node can be the same).

Assumptions

• ​The root of the given binary tree is not null

Examples

-1

/ \

2 11

/ \

6 -14

one example of paths could be -14 -> 11 -> -1 -> 2

another example could be the node 11 itself

The maximum path sum in the above binary tree is 6 + 11 + (-1) + 2 = 18

Solution: Recursive tree traversal

Base Case: root is null return 0

Recursive Rule:

From children: two max value paths

At current level: update global max is root + left + right is greater than current max

To parent: give better path between root + left and root + right