18192021222324252627282930313233343536373839404142434445

# Tree Node Definition
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    # Main function to call
    def maxPathSum(self, root):
        self.max_sum = float('-inf')
        self.dfs(root)
        return self.max_sum

    # Recursive DFS helper
    def dfs(self, node):
        if not node:
            return 0

        # Recursively find left and right max path sum
        left = max(0, self.dfs(node.left))
        right = max(0, self.dfs(node.right))

        # Update max sum if path through node is better
        self.max_sum = max(
            self.max_sum,
            left + right + node.val
        )

        # Return one-sided path
        return max(left, right) + node.val

# Driver Code
if __name__ == "__main__":
    # Build test tree
    root = TreeNode(-10)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)

    sol = Solution()
    print("Maximum Path Sum:",
          sol.maxPathSum(root))

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152

// Tree Node Definition
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    constructor() {
        this.maxSum = -Infinity;
    }

    // Main function to call
    maxPathSum(root) {
        this.dfs(root);
        return this.maxSum;
    }

    // DFS function to compute max sum
    dfs(node) {
        if (node === null) return 0;

        // Get left and right subtree max path sum
        const left = Math.max(0, this.dfs(node.left));
        const right = Math.max(0, this.dfs(node.right));

        // Update max path if node is turning point
        this.maxSum = Math.max(
            this.maxSum,
            left + right + node.val
        );

        // Return best one-sided path
        return Math.max(left, right) + node.val;
    }
}

// Driver Code
const root = new TreeNode(-10);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);

const sol = new Solution();
console.log(
    "Maximum Path Sum:",
    sol.maxPathSum(root)
);

Complexity Analysis