CareerCup

Recursively calculate the sum

int maxsum(Node *root)
{
if (root == NULL)
{
return 0;
}

return(root->val + max(maxsum(root->left),maxsum(root->right));
}

This is a problem easily solved with dynamic programming and adapted to code, here's the subproblem formula

OPT(node x) = { x.val if x is a leaf ; else max(x.val + OPT(k)) where k cycles through all children of x

in code, and this might be a bit sloppy, and assuming all children of any node t are listed in an array of nodes called t.children, looks like:

int find_max(tree t){
if (t == NULL) return 0; //this should never be reached, but its good to be secure
int max = t.val;
for(int i = 0; i < t.children.length; i++){
int q = find_max(t.children[i]);
if(t.val + q > max) { max = t.val + q);
}
return max;
}

We can break the problem in two steps
1) Get the leaf node for which sum is maximum
2) Once we have target leaf node, print the path from root to traget

public boolean printPath(BinaryNode node, BinaryNode target)
	{
		if(node == null)
		{
			return false;
		}
		
		if(node.equals(target) || printPath(node.left, target) || printPath(node.right, target))
		{
			System.out.print(node.data + "-->");
			return true;
		}
		
		return false;		
	}
	
	private int maxSum = 0;
	private BinaryNode maxSumLeaf = null;
	
	private void getMaxSumVodeLeaf(BinaryNode node, int currentSum)
	{
		if(node == null)
		{
			return;
		}
		currentSum = currentSum + node.data;
		if(node.left == null && node.right == null)
		{
			if(currentSum >= maxSum)
			{
				maxSum = currentSum;
				maxSumLeaf = node;
			}
		}
		
		getMaxSumVodeLeaf(node.left, currentSum);
		getMaxSumVodeLeaf(node.right, currentSum);
	}
	
	public int getMaxSum(BinaryNode node)
	{
		if(node == null)
		{
			return 0;
		}
		maxSum = 0;
		maxSumLeaf = null;
		
		getMaxSumVodeLeaf(node, 0);
		
		return maxSum;		
	}
	
	public int printMaxSumPath(BinaryNode node)
	{
		getMaxSum(node);
		printPath(node, maxSumLeaf);
		System.out.println();
		return maxSum;
	}

Please explain with a example. Thanks

10
/ \
8 2
/ \ \
3 11 22

Another possible solution is
1) First find the maximum Sum
2) Then print the path which has sum = maximum sum found in first step

public void findSumPath(BinaryNode node, int currentSum, String path, int sum)
	{
		if (node != null)
		{
			currentSum = currentSum + node.data;
			path = path + node.data + "-->";

			if (currentSum == sum)
			{
				System.out.println(path);
				return;
			}
			else if (currentSum < sum)
			{
				findSumPath(node.left, currentSum, path, sum);
				findSumPath(node.right, currentSum, path, sum);
			}
			else
			{
				System.out.println("No such path exists");
				return;
			}

		}
	}

	public int findMaxSum(BinaryNode node)
	{
		if (node == null)
		{
			return 0;
		}

		return (node.data + max(findMaxSum(node.left), findMaxSum(node.right)));
	}

	public int printMaxSum(BinaryNode node)
	{
		int maxSum = findMaxSum(node);
		findSumPath(node, 0, "", maxSum);
		System.out.println();
		return maxSum;
	}
	
	private int max(int value1, int value2)
	{
		if (value1 >= value2)
		{
			return value1;
		}

		return value2;
	}

[This will give you the actual path, it's easier to just get the sum]
Do preorder traversal (yes, you can do preorder traversal on N-ary trees too), such that when you go to a node you increment a running sum by the value at that node, and when you exit the node you subtract that value back.

When you reach a child, add that child's value to sum, and store both (key of child, sum to child) into a hash or DirectAccessTable.

So this is O(n) as it visits each node once..

At the end linear scan the table for max, and get the key of the child.

void maxSum( struct node *root, int *sum)
{
if( !root ) return;
int temp;
*sum = *sum + root->data;
temp = *sum;
maxSum( root->left , sum );
int lsum = *sum;
if( lsum < temp )
{
lsum = temp;
}
maxSum( root->right , &temp );
if( lsum < temp )
{
*sum = temp;
}
else
{
*sum = lsum;
}
}