# Binary Tree Maximum Path Sum

Hard — Leetcode problem

Given a **non-empty** binary tree, find the maximum path sum.

For this problem, a path is defined as any node sequence from some starting node to any node in the tree along the parent-child connections. The path must contain **at least one node** and does not need to go through the root.

**Example 1:**

**Input:** root = [1,2,3]

**Output:** 6

**Example 2:**

**Input:** root = [-10,9,20,null,null,15,7]

**Output:** 42

**Constraints:**

- The number of nodes in the tree is in the range
`[0, 3 * 104]`

. `-1000 <= Node.val <= 1000`

Solution :

HInts : kandane’s algorithm and also recursive nature of BST.

## Approach 1: Recursion

**Intuition**

First of all, let’s simplify the problem and implement a function `max_gain(node)`

which takes a node as an argument and computes a maximum contribution that this node and one/zero of its subtrees could add.

In other words, it’s amaximum gainone could have including the node (and maybe one of its subtrees) into the path.

Hence if one would know for sure that the max path contains `root`

, the problem would be solved as `max_gain(root)`

. Unfortunately, *the max path does not need to go through the root*, and here is an example of such a tree

That means one needs to modify the above function and **to check at each step what is better** : to continue the current path or to start a new path with the current node as a highest node in this new path.

**Algorithm**

Now everything is ready to write down an algorithm.

- Initiate
`max_sum`

as the smallest possible integer and call`max_gain(node = root)`

. - Implement
`max_gain(node)`

with a check to continue the old path or to start a new path: - 1. Base case : if node is null, the max gain is
`0`

. - 2. Call
`max_gain`

recursively for the node children to compute max gain from the left and right subtrees :`left_gain = max(max_gain(node.left), 0)`

and`right_gain = max(max_gain(node.right), 0)`

. - 3. Now check to continue the old path or to start a new path. To start a new path would cost
`price_newpath = node.val + left_gain + right_gain`

. Update`max_sum`

if it's better to start a new path. - 4. For the recursion return the max gain the node and one/zero of its subtrees could add to the current path :
`node.val + max(left_gain, right_gain)`

.

**Tree Node**

Here is the definition of the `TreeNode`

which we would use in the following implementation.

`class TreeNode(object):`

""" Definition of a binary tree node."""

def __init__(self, x):

self.val = x

self.left = None

self.right = None

**Implementation**

Notice that we are looking at a path from 15-> 20 -> 7 , which is an arc kind of path not seen before.

class Solution:

def maxPathSum(self, root):

"""

:type root: TreeNode

:rtype: int

"""

def max_gain(node):

if not node:

return 0# max sum on the left and right sub-trees of node

left_gain = max(max_gain(node.left), 0)

right_gain = max(max_gain(node.right), 0)

# the price to start a new path where `node` is a highest nodeprice_newpath= node.val + left_gain + right_gain

# update max_sum if it's better to start a new path

self.max_sum = max(self.max_sum,price_newpath)

# for recursion :

# return the max gain if continue the same path

return node.val + max(left_gain, right_gain)

self.max_sum = float('-inf')

max_gain(root)

return self.max_sum

Link : https://leetcode.com/problems/binary-tree-maximum-path-sum/solution/

**Complexity Analysis**

- Time complexity: O(N), where
`N`

is number of nodes, since we visit each node not more than 2 times. - Space complexity: O(H), where H is a tree height, to keep the recursion stack. In the average case of balanced tree, the tree height H=logN,
*H*=log*N*, in the worst case of skewed tree, H=N.