Solution: Binary Tree Maximum Path Sum

Statement

Given the root of a binary tree, return the maximum sum of any non-empty path.

A path in a binary tree is defined as follows:

• A sequence of nodes in which each pair of adjacent nodes must have an edge connecting them.
  • A node can only be included in a path once at most.
  • Including the root in the path is not compulsory.

You can calculate the path sum by adding up all node values in the path. To solve this problem, calculate the maximum path sum given the root of a binary tree so that there won’t be any greater path than it in the tree.

Constraints:

• $1\leq$ Number of nodes in the tree $\leq500$.
• $-1000 \leq$ Node.value $\leq 1000$

Solution

The solution focuses on determining the maximum value obtained by traversing through nodes in the binary tree. At each node, the algorithm evaluates whether to include the left and right subtrees in the current path, but only if their contributions are positive to avoid lowering the total path sum. The maximum path sum can either pass through the current node or start a new path with it as the highest point. The global maximum sum is updated as the tree is traversed, ensuring that the highest possible sum is captured.

We’ll start by simplifying the problem. We look at the implementation of the max_contrib(node) function, which takes a node as an argument and computes a maximum contribution that this node and one or none of its subtrees can add, for example: