# 124. Binary Tree Maximum Path Sum
### Description
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.
### Constraints
### Approach
### Links
* [GeeksforGeeks](https://www.geeksforgeeks.org/find-maximum-path-sum-in-a-binary-tree/)
* [Leetcode](https://leetcode.com/problems/binary-tree-maximum-path-sum/)
* [ProgramCreek](https://www.programcreek.com/2013/02/leetcode-binary-tree-maximum-path-sum-java/)
* YouTube
### **Examples**
{% tabs %}
{% tab title="Example 1" %}
**Input:** \[1, 2, 3]
**Output:** 6
**Explanation:**
{% endtab %}
{% tab title="Example 2" %}
**Input:** \[-10, 9, 20, null, null, 15, 7]
**Output:** 42
**Explanation:**
{% endtab %}
{% endtabs %}
### **Solutions**
{% tabs %}
{% tab title="TreeNode" %}
```java
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
```
{% endtab %}
{% tab title="Solution 1" %}
```java
/**
* 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,
* in the worst case of skewed tree, H = N.
*/
class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
helper(root);
return maxSum;
}
private int helper(TreeNode node) {
if(node == null) return 0;
int leftSum = Math.max(helper(node.left), 0);
int rightSum = Math.max(helper(node.right), 0);
int sum = leftSum + node.val + rightSum;
maxSum = Math.max(maxSum, sum);
return node.val + Math.max(leftSum, rightSum);
}
}
```
{% endtab %}
{% endtabs %}
### **Follow up**
*
