Maximum Path Sum

1. You are given a binary tree.

2. You have to find the maximum path sum. The path may start and end at any node in the tree.

   Notes:

3. Node class represents the node of Binary tree.

public class Solution {
    private static class Pair {
        int sum = 0;
        String path = "";
    }

    int max = Integer.MIN_VALUE;
    String maxPath = "";

    public Pair maxPathSum(TreeNode root) {
        helper(root);
        Pair ans = new Pair();
        ans.sum = max;
        ans.path = maxPath;
        return ans;
    }

    public Pair helper(TreeNode root) {
        if (root == null)
            return new Pair();
        Pair temp = new Pair();
        Pair left = helper(root.left);
        Pair right = helper(root.right);
        // Setting max path upto root
        if (left.sum <= 0 && right.sum <= 0) {
            temp.sum = root.data;
            temp.path = Integer.toString(root.data);
        } else if (left.sum > right.sum) {
            temp.sum = root.data + left.sum;
            temp.path = left.path + " " + Integer.toString(root.data);
        } else {
            temp.sum = root.data + right.sum;
            temp.path = Integer.toString(root.data) + " " + right.path;
        }
        // Setting max path overall
        if (temp.sum > max) {
            max = temp.sum;
            maxPath = temp.path;
        }
        if (node.data + left.sum + right.sum > max) {
            max = node.data + left.sum + right.sum;
            maxPath = left.path + " " + Integer.toString(root.data) + " " + right.path;
        }
        return temp;
    }
}