Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

124. Binary Tree Maximum Path Sum

My accepted Python solution to LeetCode problem 124, Binary Tree Maximum Path Sum, running in 25ms.

  • Difficulty: Hard
  • Python
  • Runtime 25ms
  • Memory 25.7MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 25ms, memory 25.7MB, accepted 2025-12-23.

python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def maxPathSum(self, root):
        self.max_sum = float('-inf')
        
        def max_gain(node):
            if not node:
                return 0
            
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)
            
            path_sum = node.val + left_gain + right_gain
            self.max_sum = max(self.max_sum, path_sum)
            
            return node.val + max(left_gain, right_gain)
        
        max_gain(root)
        return self.max_sum

Source