Max Diametric Sum
Filed under OYO
Free read 2 of 3Implement a function that returns the maximum path sum starting from the current node and going downwards.
The question
Find the maximum diametric sum of a binary tree, defined as the maximum sum of node values on a path between any two nodes in the tree. The path does not need to pass through the root.
Constraints
- 1 <= nodes <= 10^5
- Node values can be negative
Examples
- Input
- [-10, 9, 20, null, null, 15, 7]
- Output
- 42
- Why
- The path 15 -> 20 -> 7 gives the maximum sum of 15 + 20 + 7 = 42.
Approach
Implement a function that returns the maximum path sum starting from the current node and going downwards.
At each node, calculate the sum of the path passing through it (left + right + current) and update the global maximum.
Return the current node value plus the maximum of its left or right child's path sum (or 0 if negative).
Solution
O(N) time, O(H) space
class TreeNode:
def __init__(self, val=0, l=None, r=None):
self.val, self.left, self.right = val, l, r
class Solution:
def maxPathSum(self, root) -> int:
self.res = float('-inf')
def dfs(node):
if not node: return 0
l = max(0, dfs(node.left))
r = max(0, dfs(node.right))
self.res = max(self.res, l + r + node.val)
return node.val + max(l, r)
dfs(root)
return self.res
Tips
- What they are testing: Tests post-order traversal and global state management during recursion.
- Common mistake: Not handling negative node values correctly, which might mean a path doesn't have to extend to leaves.
Related OYO questions
Collected from public candidate posts and coding forums. Updated Nov 2026.