Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Find the maximum path sum.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Approach

Java

public class BinaryTreeMaximumPathSum {
    static int res = Integer.MIN_VALUE;
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(-10);
        tree.left = new TreeNode(9);
        tree.right = new TreeNode(20);
        tree.right.left = new TreeNode(15);
        tree.right.right = new TreeNode(7);

        maxPathSum(tree);
        System.out.println(res);
    }

    // method to find the maximum
    // sum of the path
    static int maxPathSum(TreeNode root) {
        // if tree is empty
        if (root == null)
            return 0;
        // call for left subtree
        int left = maxPathSum(root.left);

        // call for right subtree
        int right = maxPathSum(root.right);

        // update x as max of left right +root data,root data
        int x = Math.max(Math.max(left, right) + root.val, root.val);
        int y = Math.max(x, left + right + root.val);
        res = Math.max(res, y);
        return x;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;


//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};

//function to find the maximum
//sum of the path
int maxPathSum(TreeNode *root,int &res)
{
    //if tree is empty
    if(root==NULL)
         return 0;
    //call for left subtree
    int left=maxPathSum(root->left,res);

    //call for right subtree
    int right=maxPathSum(root->right,res);

    //update x as max of left right +root data,root data
    int x=max(max(left,right)+root->data,root->data);
    int y=max(x,left+right+root->data);
    res=max(res,y);
    return x;
}

int main()
{
    TreeNode *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);
    int x=INT_MIN;
    int maxSum=maxPathSum(root,x);
    cout<<x<<"\n";
}