# Binary Tree Maximum Path Sum
**Difficulty:** HARD
[External](https://leetcode.com/problems/binary-tree-maximum-path-sum)
Canonical: https://scaleengineer.com/dsa/problems/binary-tree-maximum-path-sum
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Flipkart](https://scaleengineer.com/companies/flipkart), [Intuit](https://scaleengineer.com/companies/intuit), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Samsung](https://scaleengineer.com/companies/samsung), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yandex](https://scaleengineer.com/companies/yandex), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Arcesium](https://scaleengineer.com/companies/arcesium), [Patreon](https://scaleengineer.com/companies/patreon), [Datadog](https://scaleengineer.com/companies/datadog), [Baidu](https://scaleengineer.com/companies/baidu), [Directi](https://scaleengineer.com/companies/directi), [Hotstar](https://scaleengineer.com/companies/hotstar)
---
## Problem
A **path** in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence **at most once**. Note that the path does not need to pass through the root.

The **path sum** of a path is the sum of the node's values in the path.

Given the `root` of a binary tree, return _the maximum **path sum** of any **non-empty** path_.

**Example 1:**

![](https://assets.glich.co/dsa/binary-tree-maximum-path-sum/image0.jpg) 

**Input:** root = [1,2,3]
**Output:** 6
**Explanation:** The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

**Example 2:**

![](https://assets.glich.co/dsa/binary-tree-maximum-path-sum/image1.jpg) 

**Input:** root = [-10,9,20,null,null,15,7]
**Output:** 42
**Explanation:** The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

**Constraints:**

* The number of nodes in the tree is in the range `[1, 3 * 104]`.
* `-1000 <= Node.val <= 1000`

# Approaches
## Brute-Force by Treating Each Node as a Pivot
This approach considers every node in the tree as the potential "pivot" or the highest point of the maximum path. For each node chosen as the pivot, we calculate the maximum path sum that can be formed by extending downwards into its left and right subtrees. The overall maximum sum is the maximum of these values calculated for every possible pivot node.
**Time:** O(N^2) · **Space:** O(N)
**Pros:** Conceptually simpler to understand as it separates the problem into two distinct parts: iterating through pivots and calculating downward path sums.
**Cons:** Highly inefficient due to a large number of redundant calculations.; The `maxPathDown` function is called for the same nodes multiple times, leading to a poor time complexity.
### Explanation
The core idea is to iterate through all nodes of the tree. For each node `u`, we treat it as the root of a path. The path can extend from `u`'s left child downwards and from `u`'s right child downwards.

We need a helper function, let's call it `maxPathDown(node)`, which calculates the maximum sum of a path starting at `node` and going strictly downwards. The `maxPathDown(node)` function is recursive: `node.val + max(0, maxPathDown(node.left), maxPathDown(node.right))`. We take `max` with 0 to handle cases where the downward path has a negative sum; in such cases, we'd rather not extend the path.

The main algorithm iterates through each node, and for each node, it calls `maxPathDown` on its children to find the path sum where the current node is the highest point. This approach is inefficient because the `maxPathDown` function is called repeatedly for the same subtrees. For example, when processing a node `u`, we compute `maxPathDown` for its entire left subtree. Later, when we process `u`'s left child as the pivot, we re-do much of the same computation.

```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;
 *     }
 * }
 */
class Solution {
    private int overallMaxSum;

    public int maxPathSum(TreeNode root) {
        overallMaxSum = Integer.MIN_VALUE;
        traverse(root);
        return overallMaxSum;
    }

    // Traverse each node and treat it as the pivot
    private void traverse(TreeNode node) {
        if (node == null) {
            return;
        }

        // Calculate the max path sum with the current node as the pivot
        int leftPath = maxPathDown(node.left);
        int rightPath = maxPathDown(node.right);

        int leftSum = Math.max(0, leftPath);
        int rightSum = Math.max(0, rightPath);

        overallMaxSum = Math.max(overallMaxSum, node.val + leftSum + rightSum);

        // Continue to the next nodes
        traverse(node.left);
        traverse(node.right);
    }

    // Helper to compute max path sum starting at a node and going down
    private int maxPathDown(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = Math.max(0, maxPathDown(node.left));
        int right = Math.max(0, maxPathDown(node.right));
        return node.val + Math.max(left, right);
    }
}
```
### Algorithm
1. Define a helper function `maxPathDown(node)`:
   - If `node` is null, return 0.
   - Recursively find the max path down from the left child: `left = max(0, maxPathDown(node.left))`.
   - Recursively find the max path down from the right child: `right = max(0, maxPathDown(node.right))`.
   - Return `node.val + max(left, right)`.
2. In the main function `maxPathSum(root)`:
   - Initialize `max_sum = Integer.MIN_VALUE`.
   - Perform a traversal (e.g., pre-order) of the tree. For each `node` visited:
     - Calculate the max path sum going down the left subtree: `left_sum = max(0, maxPathDown(node.left))`.
     - Calculate the max path sum going down the right subtree: `right_sum = max(0, maxPathDown(node.right))`.
     - Calculate the path sum with the current `node` as the pivot: `current_max = node.val + left_sum + right_sum`.
     - Update the global maximum: `max_sum = max(max_sum, current_max)`.
   - Return `max_sum`.

## Single-Pass Recursive DFS (Post-order Traversal)
This is the most efficient approach. It solves the problem in a single pass using a recursive Depth-First Search (DFS). The key insight is to realize that for any node, the information needed by its parent is the maximum path sum starting from the current node and going downwards (in a straight line). At the same time, we can calculate the maximum path sum that has the current node as its highest point (the "pivot").
**Time:** O(N) · **Space:** O(H)
**Pros:** Highly efficient, solving the problem in a single pass with O(N) time complexity.; Elegant and concise recursive solution.
**Cons:** The logic can be slightly tricky to grasp initially, as the recursive function serves two purposes: returning a value for its caller and updating a global state.
### Explanation
We design a recursive helper function, say `maxGain(node)`, that performs a post-order traversal. This function does two things:
1.  **Return Value**: It returns the maximum path sum starting from `node` and extending downwards to one of its subtrees (left or right). This value is what the parent of `node` can use to extend its own path. The value is `node.val + max(left_gain, right_gain)`.
2.  **Global Update**: It calculates the maximum path sum with `node` as the "pivot" (i.e., the path can go down both left and right subtrees). This value is `node.val + left_gain + right_gain`. This path cannot be extended further up, so we don't return it. Instead, we use it to update a global variable that tracks the overall maximum path sum found so far.

The `left_gain` and `right_gain` are the results of the recursive calls on the left and right children, respectively. We take `max(0, recursive_call_result)` because if a subtree's maximum gain is negative, we are better off not including it in our path. The main function initializes a global maximum variable, calls the recursive helper on the root, and then returns the global maximum.

```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;
 *     }
 * }
 */
class Solution {
    int maxSum;

    public int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // Recursively get the maximum path sum from left and right subtrees
        // Discard negative path sums by taking max with 0
        int leftGain = Math.max(0, maxGain(node.left));
        int rightGain = Math.max(0, maxGain(node.right));

        // Calculate the maximum path sum with the current node as the "pivot"
        // This is a potential candidate for the overall maximum path sum
        int currentPathSum = node.val + leftGain + rightGain;
        
        // Update the global maximum sum
        maxSum = Math.max(maxSum, currentPathSum);

        // Return the maximum gain for a path that can be extended by the parent node.
        // This path must go "straight" down from the parent.
        return node.val + Math.max(leftGain, rightGain);
    }
}
```
### Algorithm
1. Initialize a variable `max_sum` to `Integer.MIN_VALUE`. This will store the final result.
2. Define a recursive function `maxGain(node)`:
   - Base Case: If `node` is null, return 0.
   - Recursively call `maxGain` for the left and right children: `left_gain = max(0, maxGain(node.left))` and `right_gain = max(0, maxGain(node.right))`. We use `max(0, ...)` to discard paths with negative sums.
   - Calculate the maximum path sum with the current `node` as the highest point: `current_max_path = node.val + left_gain + right_gain`.
   - Update the global `max_sum`: `max_sum = max(max_sum, current_max_path)`.
   - Return the maximum gain that can be extended upwards to the parent of `node`: `node.val + max(left_gain, right_gain)`.
3. In the main function, call `maxGain(root)`.
4. Return `max_sum`.

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private int ans = - 1001 ; public int MaxPathSum ( TreeNode root ) { dfs ( root ); return ans ; } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = Math . Max ( 0 , dfs ( root . left )); int right = Math . Max ( 0 , dfs ( root . right )); ans = Math . Max ( ans , left + right + root . val ); return root . val + Math . Max ( left , right ); } }
```

### Java

```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; * } * } */ class Solution { private int ans = - 1001 ; public int maxPathSum ( TreeNode root ) { dfs ( root ); return ans ; } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = Math . max ( 0 , dfs ( root . left )); int right = Math . max ( 0 , dfs ( root . right )); ans = Math . max ( ans , root . val + left + right ); return root . val + Math . max ( left , right ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var maxPathSum =
  function (root) {
    let ans = -1001;
    const dfs = (root) => {
      if (!root) {
        return 0;
      }
      const left = Math.max(0, dfs(root.left));
      const right = Math.max(0, dfs(root.right));
      ans = Math.max(ans, left + right + root.val);
      return Math.max(left, right) + root.val;
    };
    dfs(root);
    return ans;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxPathSum ( TreeNode * root ) { int ans = - 1001 ; function < int ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) { if ( ! root ) { return 0 ; } int left = max ( 0 , dfs ( root -> left )); int right = max ( 0 , dfs ( root -> right )); ans = max ( ans , left + right + root -> val ); return root -> val + max ( left , right ); }; dfs ( root ); return ans ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def maxPathSum ( self , root : Optional [ TreeNode ]) -> int : def dfs ( root : Optional [ TreeNode ]) -> int : if root is None : return 0 left = max ( 0 , dfs ( root . left )) right = max ( 0 , dfs ( root . right )) nonlocal ans ans = max ( ans , root . val + left + right ) return root . val + max ( left , right ) ans = - inf dfs ( root ) return ans
```