# Binary Tree Maximum Path Sum

This page explains Java solution to problem `Binary Tree Maximum Path Sum` using `Post Order Traversal of Tree `data structure.

## Problem Statement

Given a non-empty binary tree, find the 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 the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:
```Input: [1,2,3]
1
/ \
2   3

Output: 6
```
Example 2:
```Input: [-10,9,20,null,null,15,7]
-10
/ \
9  20
/  \
15   7

Output: 42
```

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class BinaryTreeMaximumPathSum {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
solve(root);
return max;
}

private int solve(TreeNode root) {
if(root != null) {
int left = solve(root.left);
int right = solve(root.right);

if(left <= 0 && right <= 0) {
max = Math.max(max, root.val);
return root.val;
}
else if(left <= 0) {
max = Math.max(max, right + root.val);
return root.val + right;
}
else if(right <= 0) {
max = Math.max(max, left + root.val);
return root.val + left;
}
else {
max = Math.max(max, root.val + left + right);
return root.val + Math.max(left, right);
}
}
return 0;
}
}

``````

## Time Complexity

O(N) Where
N is total number of elements in an input tree

O(1)