> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/101-200/binary-tree-maximum-path-sum.md).

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

<div align="left"><img src="/files/-MGMyY8GaJPn9seDe0-0" alt=""></div>
{% endtab %}

{% tab title="Example 2" %}
**Input:** \[-10, 9, 20, null, null, 15, 7]

**Output:** 42

**Explanation:**

<div align="left"><img src="/files/-MGMyyPrN-NvXZ7TTSdh" alt=""></div>
{% 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**

*