Binary Tree Maximum Path Sum In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Close-up of a computer screen displaying programming code in a dark environment.

Problem Statement: Binary Tree Maximum Path Sum

Given a binary tree, the task is to find the maximum path sum. The path may start and end at any node in the tree, and you are allowed to move from a node to its left or right child but not upwards to its parent.

Path Definition:

A path is a sequence of nodes in the tree where each pair of adjacent nodes in the sequence has an edge connecting them. The sum of the path is the sum of the node values along the path.

Example:

Example 1:

Input:

        -10
        /  \
      9     20
           /  \
         15    7

Output:

42

Explanation: The path with the maximum sum is 15 -> 20 -> 7, which sums to 15 + 20 + 7 = 42.

Example 2:

Input:

        1
       / \
      2   3

Output:

6

Explanation: The path with the maximum sum is 2 -> 1 -> 3, which sums to 2 + 1 + 3 = 6.

Approach:

  1. Recursive Approach:
    • We will perform a DFS (Depth-First Search) traversal of the binary tree.
    • For each node, we need to calculate the maximum path sum that can be formed either including this node alone or including this node with one of its subtrees.
    • For each node:
      • The maximum path sum at this node can be either just the node itself or the node’s value plus the maximum path sum from one of its child nodes.
      • Additionally, we must also check if the sum of the current node, left child, and right child forms a maximum path that “splits” at this node.
    • The result should be the maximum of all possible paths encountered during the DFS traversal.
  2. Dynamic Programming:
    • Use a helper function to return the maximum path sum from a given node. The idea is to propagate the best possible sum upwards from the leaves of the tree.
    • Keep track of the global maximum sum encountered.
  3. Time Complexity: O(N), where N is the number of nodes in the tree, because we traverse each node exactly once.
  4. Space Complexity: O(H), where H is the height of the tree, due to the recursive call stack (worst case: O(N) for skewed trees).

Algorithm:

  1. Define a helper function to calculate the maximum path sum from each node.
  2. At each node:
    • Compute the maximum sum including the node and its left or right child (but not both).
    • Compute the maximum sum that passes through the node (including both left and right).
  3. Track the global maximum as you recursively traverse the tree.

Code Implementation:

1. C:

#include <stdio.h>
#include <limits.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int maxPathSumHelper(struct TreeNode* root, int* globalMax) {
    if (root == NULL) {
        return 0;
    }
    
    int left = maxPathSumHelper(root->left, globalMax);
    int right = maxPathSumHelper(root->right, globalMax);
    
    int maxSingle = (left > right) ? left : right;
    maxSingle = (maxSingle > 0) ? maxSingle + root->val : root->val;

    int maxTop = left + right + root->val;
    *globalMax = (*globalMax > maxTop) ? *globalMax : maxTop;
    
    return maxSingle;
}

int maxPathSum(struct TreeNode* root) {
    int globalMax = INT_MIN;
    maxPathSumHelper(root, &globalMax);
    return globalMax;
}

int main() {
    struct TreeNode n1 = { -10, NULL, NULL };
    struct TreeNode n2 = { 9, NULL, NULL };
    struct TreeNode n3 = { 20, NULL, NULL };
    struct TreeNode n4 = { 15, NULL, NULL };
    struct TreeNode n5 = { 7, NULL, NULL };
    
    n1.left = &n2;
    n1.right = &n3;
    n3.left = &n4;
    n3.right = &n5;
    
    printf("Maximum Path Sum: %d\n", maxPathSum(&n1));
    return 0;
}

2. C++:

#include <iostream>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int maxPathSumHelper(TreeNode* root, int& globalMax) {
        if (!root) return 0;
        
        int left = max(0, maxPathSumHelper(root->left, globalMax));
        int right = max(0, maxPathSumHelper(root->right, globalMax));
        
        int localMax = left + right + root->val;
        globalMax = max(globalMax, localMax);
        
        return max(left, right) + root->val;
    }

    int maxPathSum(TreeNode* root) {
        int globalMax = INT_MIN;
        maxPathSumHelper(root, globalMax);
        return globalMax;
    }
};

int main() {
    TreeNode n1(-10), n2(9), n3(20), n4(15), n5(7);
    n1.left = &n2;
    n1.right = &n3;
    n3.left = &n4;
    n3.right = &n5;
    
    Solution sol;
    cout << "Maximum Path Sum: " << sol.maxPathSum(&n1) << endl;
    
    return 0;
}

3. Java:

class Solution {
    int maxPathSumHelper(TreeNode root, int[] globalMax) {
        if (root == null) return 0;
        
        int left = Math.max(0, maxPathSumHelper(root.left, globalMax));
        int right = Math.max(0, maxPathSumHelper(root.right, globalMax));
        
        int localMax = left + right + root.val;
        globalMax[0] = Math.max(globalMax[0], localMax);
        
        return Math.max(left, right) + root.val;
    }

    public int maxPathSum(TreeNode root) {
        int[] globalMax = { Integer.MIN_VALUE };
        maxPathSumHelper(root, globalMax);
        return globalMax[0];
    }
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Main {
    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(-10);
        TreeNode n2 = new TreeNode(9);
        TreeNode n3 = new TreeNode(20);
        TreeNode n4 = new TreeNode(15);
        TreeNode n5 = new TreeNode(7);
        
        n1.left = n2;
        n1.right = n3;
        n3.left = n4;
        n3.right = n5;
        
        Solution sol = new Solution();
        System.out.println("Maximum Path Sum: " + sol.maxPathSum(n1));
    }
}

4. Python:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def maxPathSumHelper(self, root, globalMax):
        if not root:
            return 0
        
        left = max(0, self.maxPathSumHelper(root.left, globalMax))
        right = max(0, self.maxPathSumHelper(root.right, globalMax))
        
        localMax = left + right + root.val
        globalMax[0] = max(globalMax[0], localMax)
        
        return max(left, right) + root.val
    
    def maxPathSum(self, root: TreeNode) -> int:
        globalMax = [float('-inf')]
        self.maxPathSumHelper(root, globalMax)
        return globalMax[0]

# Example usage
if __name__ == "__main__":
    n1 = TreeNode(-10)
    n2 = TreeNode(9)
    n3 = TreeNode(20)
    n4 = TreeNode(15)
    n5 = TreeNode(7)
    
    n1.left = n2
    n1.right = n3
    n3.left = n4
    n3.right = n5
    
    sol = Solution()
    print("Maximum Path Sum:", sol.maxPathSum(n1))

5. C#:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public int MaxPathSumHelper(TreeNode root, ref int globalMax) {
        if (root == null) return 0;
        
        int left = Math.Max(0, MaxPathSumHelper(root.left, ref globalMax));
        int right = Math.Max(0, MaxPathSumHelper(root.right, ref globalMax));
        
        int localMax = left + right + root.val;
        globalMax = Math.Max(globalMax, localMax);
        
        return Math.Max(left, right) + root.val;
    }

    public int MaxPathSum(TreeNode root) {
        int globalMax = int.MinValue;
        MaxPathSumHelper(root, ref globalMax);
        return globalMax;
    }
}

// Example usage:
class Program {
    static void Main(string[] args) {
        TreeNode n1 = new TreeNode(-10);
        TreeNode n2 = new TreeNode(9);
        TreeNode n3 = new TreeNode(20);
        TreeNode n4 = new TreeNode(15);
        TreeNode n5 = new TreeNode(7);
        
        n1.left = n2;
        n1.right = n3;
        n3.left = n4;
        n3.right = n5;
        
        Solution sol = new Solution();
        Console.WriteLine("Maximum Path Sum: " + sol.MaxPathSum(n1));
    }
}

6. JavaScript:

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    maxPathSumHelper(root, globalMax) {
        if (!root) return 0;
        
        let left = Math.max(0, this.maxPathSumHelper(root.left, globalMax));
        let right = Math.max(0, this.maxPathSumHelper(root.right, globalMax));
        
        let localMax = left + right + root.val;
        globalMax[0] = Math.max(globalMax[0], localMax);
        
        return Math.max(left, right) + root.val;
    }

    maxPathSum(root) {
        let globalMax = [Number.NEGATIVE_INFINITY];
        this.maxPathSumHelper(root, globalMax);
        return globalMax[0];
    }
}

// Example usage
let n1 = new TreeNode(-10);
let n2 = new TreeNode(9);
let n3 = new TreeNode(20);
let n4 = new TreeNode(15);
let n5 = new TreeNode(7);

n1.left = n2;
n1.right = n3;
n3.left = n4;
n3.right = n5;

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

Summary:

  • Time Complexity: O(N), where N is the number of nodes.
  • Space Complexity: O(H), where H is the height of the tree (due to recursion).