**Maximum Path Sum in a Binary Tree**

Asked in:Directi, Amazon

Difficulty:Medium

**Understanding the Problem**

**Problem description: **Given a non-empty binary tree, find maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along with the parent-child connections.

**Note**: The path may start and end at any node of the tree.

**Example 1:**

```
Input: 1
/ \
2 3
```

`Output: 1+2+3 = 6`

**Example 2:**

```
Input: 5
/ \
-1 8
/ / \
11 13 7
/ \ \
-7 2 -1
```

`Output: 13+8+7 = 28`

The node structure for the BST passed to your function will be

```
class TreeNode{
int val
BSTNode left
BSTNode right
}
```

**Possible questions to ask the interviewer:**

- Could the node value be negative? (
**Ans:**Yes)

**Brute force and Efficient solutions**

We will be discussing two possible solutions for this problem:

**Brute force approach**: Traverse left and right subtree of each node and calculate maximum possible sum path.**Recursive approach:**We calculate the maximum path sum rooted at each node and update the max sum during the traversal.

**1. Brute Force**

We can update the max path sum passing through each node T in the tree by traversing the T's left subtree and right subtree.

Solution steps

- Assume we have nodes numbered 1 to N
- sum(i) = Maximum sum of a path containing node(i). Clearly the solution of the problem is max(sum(1), sum(2), ...., sum(N))
- Now, what is the maximum sum of a path containing a particular node(i)?
- left_result: maximum path sum starting at node(i).left
- right_result: maximum path sum starting at node(i).right
- sum(i) = max(left_result, 0) + max(right_result, 0) + node(i).val

Pseudo Code

`//driver function`

```
int maxPathSum(TreeNode root){
int answer = INT_MIN
answer = max_path_sum_helper(root, answer)
return answer
}
```

```
void helper(TreeNode root, int sum_so_far, int &result){
if(root == NULL)
return
result = max(result, sum_so_far + root.val)
helper(root.left , sum_so_far + root.val, result)
helper(root.right, sum_so_far + root.val, result)
}
```

```
void max_path_sum_helper(TreeNode root, int &answer){
if(root is NULL)
return
left_result = INT_MIN
right_result = INT_MAX
// Find maximum path sum starting from root.left
helper(root.left , 0, left_result )
// Find maximum path sum starting from root.right
helper(root.right, 0, right_result)
left_result = max(left_result , 0)
right_result = max(right_result, 0)
answer = max(left_result + right_result + root.val, answer)
max_path_sum_helper(root.left, answer)
max_path_sum_helper(root.right, answer)
}
```

Complexity Analysis

**Time Complexity:** Time complexity for sum(i) is O(N). The total time complexity is **O(N²)**. **(Think!)**

**Space Complexity**: Space complexity is O(N).

Critical ideas to think!

- How can you try to compute the max sum for any node if you have the max sum for their left and right sub-tree?
- Why did we take max(left_result, 0) in the function max_path_sum_helper()?

**2. Recursive Approach**

Each node can be the root of the final maximum path sum. The root here means the topmost node in a path. We calculate the maximum Path Sum rooted at each node and update the max sum during the traversal.

There can only be four different cases when a particular node is involved in the max path.

- Its the only Node
- Max path through Left Child + Node
- Max path through Right Child + Node
- Max path through Left Child + Node + Right Child

In this algorithm, we can use post-order traversal and return the maximum sum in the subtree starting from the root. We call it left_result and right_result for left and right subtree

Pseudo Code

`// driver function`

```
int maxPathSum(TreeNode root){
max_so_far = INT_MIN
max_so_far = helper(root, max_so_far)
return max_so_far
}
```

```
int helper(TreeNode root, int max_so_far){
if(root is NULL){
return 0
}
int left_result = max(0, helper(root.left, max_so_far))
int right_result = max(0, helper(root.right, max_so_far))
max_so_far = max(left_result + right_result + root.val, max_so_far)
// return maximum sum starting from root
return max(left_result, right_result, 0) + root.val
}
```

Complexity Analysis

*We are traversing each node only once.***Time Complexity = **O(N), where N is the total number of nodes. **(Think!)**

**Space Complexity : **O(h), where h is the maximum height of the tree.

Critical Idea to think

- How we are computing the answer for any vertex if we have an answer for their left and right child?
- The root of every subtree needs to return maximum path sum such that at most one child of root is involved.
**(Why?)** - Are we able to keep track of all the four possibilities discussed above?

**Comparison of the two solutions**

**Suggested problems to solve**

- Convert binary tree to mirror tree
- Maximum sum path between two leaves in a binary tree
- Find the diameter of a binary tree

Please comment down below if you have alternative approaches or find an error/bug in the above approaches.

**Happy coding!**