CareerCup

public static void main(String[] args)
    {
TreeNode root = createTree();
TreeSum maxSum = findMaxSum(root);
        System.out.println(Math.max(maxSum.maxSumBetweenTwoNodes, maxSum.maxSumFromRootToLeaf));
}

private static class TreeNode
    {
        private int data;
        private TreeNode left;
        private TreeNode right;

        public int getData()
        {
            return data;
        }

        public TreeNode getLeft()
        {
            return left;
        }

        public TreeNode getRight()
        {
            return right;
        }

        public TreeNode(int data)
        {
            this.data = data;
            left = null;
            right = null;
        }

        public void setLeft(TreeNode left)
        {
            this.left = left;
        }

        public void setRight(TreeNode right)
        {
            this.right = right;
        }
    }

private static TreeNode createTree()
    {
        /* Create following Binary Tree
                     
                      1
                    /   \
                  2       3
                 / \     / \
                4   5   11  12

        */
        TreeNode root = new TreeNode(1);
        root.setLeft(new TreeNode(2));
        root.setRight(new TreeNode(3));
        root.getLeft().setLeft(new TreeNode(4));
        root.getLeft().setRight(new TreeNode(5));
        root.getRight().setLeft(new TreeNode(11));
        root.getRight().setRight(new TreeNode(12));
        return root;
    }

private static class TreeSum
    {
        private int maxSumBetweenTwoNodes;
        private int maxSumFromRootToLeaf;

        public TreeSum(int maxSumBetweenTwoNodes, int maxSumFromRootToLeaf)
        {
            this.maxSumBetweenTwoNodes = maxSumBetweenTwoNodes;
            this.maxSumFromRootToLeaf = maxSumFromRootToLeaf;
        }
    }

    private static TreeSum findMaxSum(TreeNode root)
    {
        if (root == null)
        {
            return new TreeSum(0, 0);
        }
        TreeSum leftTreeSum = findMaxSum(root.getLeft());
        TreeSum rightTreeSum = findMaxSum(root.getRight());
        int maxSumBetweenTwoNodesOfChildren =
                Math.max(leftTreeSum.maxSumBetweenTwoNodes, rightTreeSum.maxSumBetweenTwoNodes);
        maxSumBetweenTwoNodesOfChildren =
                Math.max(maxSumBetweenTwoNodesOfChildren, leftTreeSum.maxSumFromRootToLeaf
                        + rightTreeSum.maxSumFromRootToLeaf + root.getData());
        int maxSumFromRootToLeaf =
                leftTreeSum.maxSumFromRootToLeaf > rightTreeSum.maxSumFromRootToLeaf
                        ? leftTreeSum.maxSumFromRootToLeaf + root.getData()
                        : rightTreeSum.maxSumFromRootToLeaf + root.data;
        return new TreeSum(maxSumBetweenTwoNodesOfChildren, maxSumFromRootToLeaf);
    }

/* C code */
typedef struct node {
	int data;
	struct node *left;
	struct node *right;
} Node;

/* To begin with, pass pointer to root node */
int MaxPathSum (Node *node) {
	int leftSubtreeSum, rightSubtreeSum;

	/* NULL check */
	if (node == NULL) return 0;

	/* Leaf node check */
	if (node->left == NULL && node->right == NULL)
		return node->data;

	leftSubtreeSum = MaxPathSum (node->left);
	rightSubtreeSum = MaxPathSum (node->left);

	if ( leftSubtreeSum  > rightSubtreeSum )
		return leftSubtreeSum  + node->data;
	
	else
	/* else is redundant. You don't need an else.
	 * You can directly use the return below without else.
	*/
	return rightSubtreeSum  + node->data;
}

/* Begin with sum as 0 and max as root->info*/
int maxPathSum(Node root, int sum, int max)
{
    if(root == NULL)
     return max;
    int newSum;
    int newMax;
    
    if(sum<0)
     newSum = root->info;
    else
      newSum = root->info + sum;
    
    int lMax,rMax;
    if(newSum > max)
       newMax = newSum;
    else
       newMax = max;
     
    int lMax = maxPathSum(root->left, newSum, newMax);
    int rMax = maxPathSum(root->right,newSum, newMax);
  
    if(lMax > rmax)
     return lMax;
    else
     return rMax;
          
}

tested, it works well

int maxPathSum(BTREE *root)
{
int lMaxSum=0, rMaxSum=0;

if(root == NULL)
return 0;

//if this is a leaf, then return o
if(root->left == NULL && root->right == NULL)
return 0;

if(root->left != NULL)
{
lMaxSum = maxPathSum(root->left);
}

if(root->right != NULL)
{
rMaxSum = maxPathSum(root->right);
}

if(root->parent != NULL)
{
if(lMaxSum > rMaxSum)
{
return lMaxSum + root->data;
}else
{
return rMaxSum + root->data;
}

}else if(root->parent == NULL)
{
if(root->left != NULL && root->right != NULL)
{
return lMaxSum+rMaxSum+root->data;
}else if(root->left == NULL)
{
return rMaxSum;
}else if(root->right == NULL)
{
return lMaxSum;
}
}

}

This is a fairly tough problem, but it can be attacked recursively. For any root node, there are up to five paths/values to consider. You have up to two "maximum" paths on the left side, one of which is disconnected from the root node (potentially) and one of which is connected. Then you have the same on the right side. Then you have the value of the root node itself.

Given 5 subpaths, there are 32 ways to combine them, but not all of those combinations form valid paths themselves. So you can prune some combinations as obviously invalid, due to either having overlapping values or not being connectable.

The question doesn't clarify that the binary tree is actually a sort tree--i.e. all elements to the left of the root node are less than the root node--but if you did know that property, you could prune even further.

This might not adhere to all constraints, but can be solved using the solution below.

The solution can be achieved in linear time using recursion. The idea is to find the max sum in left and right sub trees for a node and return the largest of those numbers along with the path to that node. The root of the tree will finally compare the max numbers in its left and right sub trees and returns the larger of those two numbers along with the path.

linearspacetime[dot]blogspot[dot][com]

public void MaxSumPath(Node<int> node, ref int maxSum, int sum, List<Node<int>> path, List<Node<int>> resultPath)
{
if (node == null)
{
if (sum > maxSum)
{
resultPath.Clear();

foreach (var n in path)
{
resultPath.Add(n);
}

maxSum = sum;
}
return;
}

path.Add(node);
MaxSumPath(node.Left, ref maxSum, sum + node.Value, path, resultPath);
MaxSumPath(node.Right, ref maxSum, sum + node.Value, path, resultPath);
path.Remove(node);
}

Given that someone half-retarded wrote the problem statement: can someone (preferably someone capable of expressing coherent thoughts in English) re-word it so that it can be understood in English?

similar as finding the diameter of the tree, recursively find out the max sum of the path in the left or right subtree and max sum of the path from the left child or right child

max = max(val + (left_max_from_root > 0 ? left_max_from_root : 0) + (right_max_from_root > 0 ? right_max_from_root : 0),
left_max,
right_max)

max_from_root = max(val, left_max_from_root + val, right_max_from_root + val)

class MaxSum
        {
                public int max; //max sum of the path in the tree (not necessary includind the root)
                public int maxFromRoot; //max sum of the path from the root (not necessary to the leaf node)
 
                public MaxSum(int max, int maxFromRoot)
                {
                        this.max = max;
                        this.maxFromRoot = maxFromRoot;
                }
        }
 
        public MaxSum maxSum(TreeNode root)
        {
                if(root == null) return new MaxSum(0, 0);
                MaxSum leftSum = maxSum(root.left);
                MaxSum rightSum = maxSum(root.right);
                int maxFromRoot = Math.max(root.val, Math.max(leftSum.maxFromRoot + root.val, rightSum.maxFromRoot + root.val));
                int max = root.val + 
                        (leftSum.maxFromRoot > 0 ? leftSum.maxFromRoot : 0) + 
                        (rightSum.maxFromRoot > 0 ? rightSum.maxFromRoot : 0);
                max = Math.max(max, Math.max(leftSum.max, rightSum.max));
                return new MaxSum(max, maxFromRoot);
        }

In tested it for many cases and It works true:)

public static int max_sum = Integer.MIN_VALUE;
	public static void find_max_sum(Node root,ArrayList<Node> list){
		if(root == null) return;
		list.add(root);
		int sum = 0;
		for(Node c : list){
			sum+=(int)c.data;
			if(sum > max_sum){
				max_sum = sum;
			}
		}
		find_max_sum(root.left, list);
		find_max_sum(root.right,list);
		list.remove(root);
		
	}
		
	public static void main(String[] args) throws Exception {
		Node n1 = new Node(5);
		Node n2 = new Node(2);
		Node n3 = new Node(-4);
		Node n4 = new Node(-1);
		Node n5 = new Node(-3);
		Node n6 = new Node(-2);
		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n2.right = n5;
		n3.left = n6;
		find_max_sum(n1, new ArrayList<Node>());
		System.out.println(max_sum);
	}

understand why such recurstion lsum, rsum and result is passed with pointer here at with same code and same example :
www . gohired . in / 2015/05/maximum-path-sum-between-two-leaves

gohired dot in/2015/05/maximum-path-sum-between-two-leaves

gohired dot in 2015 05 maximum-path-sum-between-two-leaves