# 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:

Example 2:

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 a maximum gain one 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.

Implementation

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

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=log⁡N, H=logN, in the worst case of skewed tree, H=N.

## More from Technical Interviews Preparation

Currently preparing for interviews

## How to Convert Strings to Booleans in Ruby

Get the Medium app