CareerCup

My solution , verified ...

int 	max(int a, int b)
{
	return a>b ? a: b;
}
int	maxPath(NodePosition root)
{
	if ( root == NULL)
		return 0;

	return root->Element + max(maxPath(root->Left), maxPath(root->Right));
}

void  DoPrintMaxPath(NodePosition root, vector<int> &path, int maxsum, int &sum)
{
	if ( root == NULL )
		return ;

	// enter a node
	path.push_back(root->Element);
	sum += root->Element;

	if (!root->Left&&!root->Right && sum == maxsum )
	{
		// reach the max path
		for( int i = 0; i < path.size(); i++)
			cout << path[i] << endl;
		return ;
	}
	DoPrintMaxPath(root->Left, path, maxsum, sum);
	DoPrintMaxPath(root->Right, path, maxsum, sum);
	path.pop_back();
	sum -=root->Element;
}

void   PrintMaxPath(NodePosition root)
{
	vector<int>  path;
	int maxsum = maxPath(root);
	int sum = 0;
	cout << "Max Length:" << maxsum << endl;
	DoPrintMaxPath(root, path, maxsum, sum);
}

its very similar to finding the longest sub sequence of an integer array. As the integer can be negative, we have to include the node under consideration into the sub optimal solution only even after adding it the solution remains positive.

Solution:
start from root with dfs approach. keep on traversing towards the bottom till the point when adding the node value to the sum will yield non negative value. once this situation has arrived, it means we cannot add the new node to the solution and this is the max sum this traversal can yield from ROOT. compare this sum with the "Global Maximum" sum value and update it. if "Global Maximum" sum is less than the sum, "Global maximum" sum = the sum.
No need to further traverse down the tree from the node(as the solution is required from the ROOT TO LEAF).

Do this for the dfs traversal and the solution will be the "Global maximum" sum.
Time complexity: o(n)
space complexity: o (1)


Another nice add on to show creativity. think about doing the same with multiple threads (parallel way). the whole tree can be divided equally among the present number of threads: if there are 4 threads, we can divide the tree into four subtrees. we can get four subtrees at second level (2^n subtrees at each level).

public Linklist<Node> path = new LinkList<Node>();

int msp(Node root){
if(root == null)
return 0;

int leftSum = msp(root.left);
int rightSum = msp(root.right);

if(leftSum > rightSum){
add left path into linklist;
} else {
add right path into linklist;
}

int sum = root.value + max(leftSum, rightSum);

}

void pathWithMaxSum(node *root, int A[]){

static int index = 0, max = -1, path[10] ,sum = 0;

if(root == NULL) {

//printf("%d %d\n", sum , index);
path[index]=-1;
int i=0;
if(sum > max){
while(1){
A[i]=path[i];
if(path[i]==-1) break;
i++;
}
max = sum ;
return ;
}
}

else {

path[index] = root->data;
index++;
sum=sum+root->data;
pathWithMaxSum(root->left,A);
pathWithMaxSum(root->right,A);
index--;
sum=sum-root->data;

}
}

void maxSumPath (node* root, int* maxSum, int* path, int level, int curSum)
{
	int currPath[100];
	if(root)
	{
		currPath[level] = root->data;
		curSum = curSum + root->data;
		maxSumPath (root->left, maxSum, path, level+1, curSum);
		maxSumPath (root->right, maxSum, path, level+1, curSum);
	}
	else
	{
		int i;
		if(*maxSum<curSum)
		{
			path[0]=level-1; /*first value will tell the length of muxSumPath*/
			for (i=0; i<level-1; i++)
			{
				path[i+1]=currPath[i];
			}
			*maxSum = curSum;
		}
	}
}

void printMaxSumPath (node* root)
{
	int path[100], index, maxSum=0;
	maxSumPath (root,&maxSum,path,0,0);
	for(index=0; index<path[0]; index++)
	{
		printf("[%d]", path[index+1]);
	}
	printf("\n");
}

<pre lang="" line="1" title="CodeMonkey88220" class="run-this">1. Find the Maximum root to leaf node path while keeping the leaf node O(n).
2. Print the root to leaf node path using this leaf node. O(n)

It works for negative numbers also.

void findMaxSumLeaf(Node *root, Node ** leaf, int curSum, int *sum){
if(root == NULL)
return;
curSum = curSum + root->data;
if(root->left == NULL && root->right == NULL){
if(curSum > *sum){
*sum = curSum;
*leaf= root;
}
}
findMaxSumLeaf(root->left, leaf, curSum, sum);
findMaxSumLeaf(root->right, leaf, curSum, sum);
}

void printRootToLeafHelper(Node* node, Node * leaf) {
int path[1000];
printRootToLeaf(node, leaf, path, 0);
}

void printRootToLeaf(Node* node, Node * leaf, int path[], int pathLen) {
if (node==NULL) return;
path[pathLen++] = node->data;
if (node == leaf && node->left==NULL && node->right==NULL)
printArray(path, pathLen);
else {
printRootToLeaf(node->left, leaf, path, pathLen);
printRootToLeaf(node->right, leaf, path, pathLen);
}
}

void printArray(int arr[], int len) {
int i;
for (i=0; i<len; i++)
printf("%d ", arr[i]);
}

</pre><pre title="CodeMonkey88220" input="yes">
</pre>

since it satisfies optimal substructure & overlapping sub problem property. we can apply dynamic programming method.

"if the given NODE is a leaf node, we just return the given nodes value, else MAX{msp(NODE.left), msp(NODE.right)}, where msp(NODE) returns the Maximum Sum path value of the given NODE as root.

max_sum(node *n)
{
int sum = 0, max = n->value;

if(n->left == NULL && n->right == NULL)
return max;
else if(n->left == NULL)
sum = max_sum(n->right);
else
sum = max_sum(n->left);
if(sum > 0)
{
if(max > 0)
max += sum;
else
max = sum;
}
return max;
}

int find_max_sum(node *root)
{
retutn max_sum(root);
}

<pre lang="" line="1" title="CodeMonkey44612" class="run-this">public void findMaximumSumPath(Node root) {
if (root.left != null) {
findMaximumSumPath(root.left);
}

if (root.right != null) {
findMaximumSumPath(root.right);
}

if (root != null) {
root.maxSum = root.value;
}

if (root.left != null && root.right != null) {
root.maxSum += ((root.left.maxSum > root.right.maxSum) ?
root.left.maxSum : root.right.maxSum);
} else if (root.left != null) {
root.maxSum += root.left.maxSum;
} else if (root.right != null) {
root.maxSum += root.right.maxSum;
}
}
</pre><pre title="CodeMonkey44612" input="yes">
</pre>

<pre lang="" line="1" title="CodeMonkey54179" class="run-this">vector<int> calculateMaxSumPath(vector<int> out, int& sum, TreeNode* root){

if(root->left == NULL && root->right == NULL){
sum+=root->data;
out.push_back(root->data);
return out;
}

sum += root->data;
int temp = sum;
out.push_back(root->data);

vector<int> out1 = calculateMaxSumPath(out, sum, root->left);
int leftSum = sum;
vector<int> out2 = calculateMaxSumPath(out, temp, root->right);
int rightSum = temp;

if(leftSum > rightSum)
return out1;

else
return out2;

}

int main(){

int sum = 0;
vector<int> temp;
vector<int> out = calculateMaxSumPath(temp, sum, root);

cout<<"Printing maximum sum path"<<endl;

for(int i=0;i<out.size();i++)
cout<<out[i]<<" ";

cout<<endl;

return 0;
}</pre><pre title="CodeMonkey54179" input="yes">
</pre>

int summax(node* root)
{

if(root==NULL)
 return 0;
else
if(summax(root->left)>summax(root->right)
printf("%d",root->left->data);
else 
printf("%d",root->right->data);

return MAX(summax(root->left),summax(root->right))+root->data;
}

If we are allowed to change the structure of linked list (which very often we are not) we can store an extra char variable in the node which just stores 'L' if left is greater otherwise it stores 'R'. When traversing the calculateMaxSum() function we fill this char variable with respective values. After complete traversal we just start from root, printing the elements, go left if the char variable says L otherwise we'll go right. Time Complexity: O(n) Space Complexity: O(n)

If we are not allowed to change the structure then we can create a new tree which just stores whether to go left or right while printing the sum. The program follows. Here also Time Complexity: O(n) Space Complexity: O(n)

<pre lang="" line="1" title="CodeMonkey20684" class="run-this">#include"tree.cpp"

struct path{
char where;
path *left;
path *right;
};

struct node{
int data;
node *left;
node *right;
};

int printLargestSumPath(node *root,path **head);

int main()
{
node *root=createTree();
cout<<"\nThe tree has been constructed";
path *head=NULL;
int sum=printLargestSumPath(root,&head);

//Print the path with largest sum
cout<<"\nThe path with largest sum is:\n";
node *temp=root;
while(temp){
cout<<temp->data<<" ";
if(head->where=='L'){
temp=temp->left;
head=head->left;
}
else{
temp=temp->right;
head=head->right;
}
}

cout<<"\nThe largest root to leaf sum is: "<<sum;
cin.ignore(2);
return 0;
}

int printLargestSumPath(node *root,path **head)
{
if(!root) return 0;

path *pl,*pr;
pl=pr=NULL;
int lsum=printLargestSumPath(root->left,&pl);
int rsum=printLargestSumPath(root->right,&pr);

path *temp=new path;
temp->left=pl;
temp->right=pr;
*head=temp;

if(lsum>=rsum){
temp->where='L';
return (lsum+root->data);
}
else{
temp->where='R';
return (rsum+root->data);
}

}



</pre><pre title="CodeMonkey20684" input="yes">
</pre>

int msp(node * root, llnode ** cur_path)
{
int ls,rs,sum;
llnode *l,*r;
append(cur_path, root);
ls=msp(root->left,&l);
rs=msp(root->right,&r);
if(ls>rs)
{
      append(cur_path,l);
      sum+=ls;
      return sum;
}
else
{
      append(cur_path,r);
      sum+=ls;
      return sum;
}
}

maxPathSum(TreeNode* root, int run_sum, list<TreeNode*> path, list<TreeNode*>& maxPath, int maxSum)
{
      if (root == NULL) return NULL;
      run_sum += root->val;
      path.push_back(root);
      if (root->left == NULL && root->right == NULL)
      {
                   if (run_sum > max_sum)
                   {
                                  minPath = path;
                                  max_sum = run_sum;
                    }
      }
      else
      {
                  maxPathSum(root->left, run_sum, path, maxSum, maxPath);
                  maxPathSum(root->right,  run_sum, path, maxSum, maxPath);
       }
}