Question:

How to calculate the maximum path sum between 2 Special Nodes?

Summary:

Suppose we have a binary tree in which each node element contains a number. With the code below, we will find out the maximum possible path we can generate from one special node to another.

Solution:

//User function Template for Java

/* class Node

{

int data;

Node left, right;

Node(int item)

{

data = item;

left = right = null;

}

} */

class Solution {

private int sum;

public Solution() {

this.sum = Integer.MIN_VALUE;

}

int findMaxPathSum(Node root) {

if (root == null) {

return 0;

}

int lsum = findMaxPathSum(root.left);

int rsum = findMaxPathSum(root.right);

if (root.left == null && root.right == null) {

return root.data;

}

if (root.left == null) {

return root.data + rsum;

}

if (root.right == null) {

return root.data + lsum;

}

this.sum = Math.max(this.sum, root.data + lsum + rsum);

return Math.max(root.data + lsum, root.data + rsum);

}

int maxPathSum(Node root) {

int ans = findMaxPathSum(root);

if (root.left == null || root.right == null) {

this.sum = Math.max(this.sum, ans);

}

return this.sum;

}

Explanation:

This Java code defines a class Solution that contains methods for finding the maximum path sum in a binary tree. Here's a breakdown of the code:

private int sum;: This declares a private integer variable sum which will be used to store the maximum path sum found during the traversal of the binary tree.
public Solution() { this.sum = Integer.MIN_VALUE; }: This is a constructor for the Solution class. It initializes the sum variable with the minimum value of Integer.
int findMaxPathSum(Node root): This method recursively calculates the maximum path sum starting from the given root node. It returns the maximum path sum that can be obtained starting from root node.
Inside the method, it calculates the maximum path sum of the left subtree (lsum) and right subtree (rsum).
If root is a leaf node, it returns its value.
If root has only one child (either left or right), it returns the sum of root.data and the maximum path sum of the non-null child.
If root has both left and right children, it updates the sum variable to store the maximum path sum found so far, and returns the maximum of the sum including root.data with either the left subtree or the right subtree.
int maxPathSum(Node root): This method is the entry point for finding the maximum path sum. It calls the findMaxPathSum method to calculate the maximum path sum.
If the root has only one child (either left or right), it updates the sum variable to store the maximum of the current sum and the maximum path sum found so far (ans).
Finally, it returns the maximum path sum stored in the sum variable.