# Maximum Path Sum Binary Tree I

Medium

Given a binary tree in which each node contains an integer number. Find the maximum possible sum **from one leaf node to another leaf node.** If there is no such path available, return Integer.MIN\_VALUE(Java)/INT\_MIN (C++).

**Examples**

  -15

  /    \\

2      11

     /    \\

    6     14

The maximum path sum is 6 + 11 + 14 = 31.

**Solution:**

To Parent: return root.key + max(left path, right path)

At Current: update globalMax against root.key + left path + right path

From Children: largest sum left path and largest sum right path

```
public class Solution {
  public int maxPathSum(TreeNode root) {
    int[] max = new int[]{Integer.MIN_VALUE};
    helper(root, max);
    return max[0];
  }

  private int helper(TreeNode root, int[] max){
    if (root == null){
      return 0;
    }

    if (root.right == null && root.left == null) {
      return root.key;
    } else if (root.right == null) {
      return helper(root.left, max) + root.key;
    } else if (root.left == null) {
      return helper(root.right, max) + root.key;
    } else {
      //case 4
      // from children
      // get best partial paths from left and right
      int bestLPath = helper(root.left, max);
      int bestRPath = helper(root.right, max);

      // at current
      // compare completeLocalPath to global maximum path
      int completeLocalPath = bestLPath + root.key + bestRPath;
      max[0] = Math.max(max[0], completeLocalPath);

      // to parent
      // pass up best partial path
      return Math.max(bestLPath, bestRPath) + root.key;
    }
  }
}

```

**Mistakes Made:**

problem constraint states a valid path must be from one leaf node to another. This means that we can only update the global maximum if we have **both** a left and right child