CareerCup

first find the max sum in tree and then search for path for max sum in the tree.
below c++ function will give you the result.
global variable: vector <int> v, int s=0 and int sum=0;

void maxSum(node * root) {
	if( root == NULL) 
		return;	
	sum += root->data;
	maxSum( root->left);
	maxSum( root->right);
	if( root->left == NULL && root->right == NULL) 
		if( s < sum ) s = sum;	
	sum -= root->data;
}
void hasPathSum( node * root, int sum) {
	if( root == NULL) return ;
	else {
		int subSum = sum - root->data;
		v.push_back( root->data);
		if( subSum == 0 && root->left == NULL && root->right ==NULL)
			for( int i=0; i<v.size(); i++) cout<<v[i]<<"->";
		hasPathSum(root->left, subSum);
		hasPathSum(root->right, subSum);
		v.pop_back();
	}
}

I have a solution but the run time is horrible (n^3 I think, correct me if wrong), I thought of a couple ways to optimize but they are complicated. If anybody knows something with better run time please post.

int findMax(Node * root)
{
    if (!root) return 0;
    return root->value + std::max(findMax(root->left), findMax(root->right));
}


void printMaximalPath(Node * root)
{
     std::cout << root->value << std::endl;
     int maxLeft = findMax(root->left);
     int maxRight = findMax(root->right);
     if (maxLeft < maxRight)
          printPath(root->right);
     else if (maxRight < maxLeft)
          printPath(root->left);
     else
          return; //Leaf node reached
}

int global_max=0;
ArrayList<TreeNode> global_max_path=null;

void findMaxPath (TreeNode t, int sum, ArrayList<TreeNode> path)
{
	if(t == null)
	{
		if(sum > global_max)
		{
			global_max=sum;
			global_max_path = path;
		}
	}
	else
	{
		 ArrayList<TreeNode> left_path = new ArrayList<TreeNode>(path);
		 findMaxPath(t.left,sum+t.data,path.add(t));
		 
		 ArrayList<TreeNode> right_path = new ArrayList<TreeNode>(path);
		 findMaxPath(t.right,sum+t.data,path.add(t));	
	}

}

findMaxPath(t,0,new ArrayList<TreeNode>());

does it mean the sum of values on the path is maximum or path to the node with max value

Binary tree we cant assume it is sort(BST), in that case I'd use a DFS(depth-first search), visiting all paths from the root. You can keep in a separeted structure the max sum found and the nodes visited.... You can even considering using a max priority queue to support it.

What is the definition of a path..start at root and ends at leaf? or start at root and ends at leaf or non-leaf node? or start at leaf and ends at leaf with/without root as an intermediate node? or start at non-leaf and end at non-leaf? or any combo?

def dfsMax(bt, n="root", path=[], maxPath=[],  maxData=None):
    #Init
    if n=="root":
        n=bt.root
    if maxData==None:
        maxData=n.data
    if n==None:
        return maxPath

    path.append(n)

    #Update Max Path    
    if n.data >maxData:
        maxPath = list(path)
        
    maxPathL=dfsMax(bt, n.left, path, maxPath, maxData)
    maxPathR=dfsMax(bt, n.right, path, maxPath, maxData)
    
    path.pop(-1)
          
    if len(maxPathL)==0:
        return maxPathR
    if len(maxPathR)==0:
        return maxPathL

    if (maxPathL[-1].data>maxPathR[-1].data):
        return maxPathL
    else:
        return maxPathR