124. Binary Tree Maximum Path Sum LeetCode Solution

In this guide, you will get 124. Binary Tree Maximum Path Sum LeetCode Solution with the best time and space complexity. The solution to Binary Tree Maximum Path Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Binary Tree Maximum Path Sum solution in C++
Binary Tree Maximum Path Sum solution in Java
Binary Tree Maximum Path Sum solution in Python
Additional Resources

124. Binary Tree Maximum Path Sum LeetCode Solution image

Problem Statement of Binary Tree Maximum Path Sum

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:

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:

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h)

124. Binary Tree Maximum Path Sum LeetCode Solution in C++

class Solution {
 public:
  int maxPathSum(TreeNode* root) {
    int ans = INT_MIN;
    maxPathSumDownFrom(root, ans);
    return ans;
  }

 private:
  // Returns the maximum path sum starting from the current root, where
  // root->val is always included.
  int maxPathSumDownFrom(TreeNode* root, int& ans) {
    if (root == nullptr)
      return 0;

    const int l = max(0, maxPathSumDownFrom(root->left, ans));
    const int r = max(0, maxPathSumDownFrom(root->right, ans));
    ans = max(ans, root->val + l + r);
    return root->val + max(l, r);
  }
};
/* code provided by PROGIEZ */

124. Binary Tree Maximum Path Sum LeetCode Solution in Java

class Solution {
  public int maxPathSum(TreeNode root) {
    maxPathSumDownFrom(root);
    return ans;
  }

  private int ans = Integer.MIN_VALUE;

  // Returns the maximum path sum starting from the current root, where
  // root.val is always included.
  private int maxPathSumDownFrom(TreeNode root) {
    if (root == null)
      return 0;

    final int l = Math.max(maxPathSumDownFrom(root.left), 0);
    final int r = Math.max(maxPathSumDownFrom(root.right), 0);
    ans = Math.max(ans, root.val + l + r);
    return root.val + Math.max(l, r);
  }
}
// code provided by PROGIEZ

124. Binary Tree Maximum Path Sum LeetCode Solution in Python

class Solution:
  def maxPathSum(self, root: TreeNode | None) -> int:
    ans = -math.inf

    def maxPathSumDownFrom(root: TreeNode | None) -> int:
      """
      Returns the maximum path sum starting from the current root, where
      root.val is always included.
      """
      nonlocal ans
      if not root:
        return 0

      l = max(0, maxPathSumDownFrom(root.left))
      r = max(0, maxPathSumDownFrom(root.right))
      ans = max(ans, root.val + l + r)
      return root.val + max(l, r)

    maxPathSumDownFrom(root)
    return ans
 # code by PROGIEZ