โ† OYO questions

Max Diametric Sum

Filed under OYO

Free read 2 of 3

Implement 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

  1. Implement a function that returns the maximum path sum starting from the current node and going downwards.

Solution

O(N) time, O(H) space

Python
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.