CareerCup

Do a post order traversal and decide the sum of the subtree and the best sum seen so far and return it to the parent. --- O(n)

Hi,

I have an O(n) algo for this. Please check it. In this, I make inorder traversal and keep on saving the max sum and the corresponding node till now in 2 variables.

int get_max_sum_node(node *root, node **max_sum_node)
{
    static int max = 0;
    
    if(root != NULL)
    {
        int sum = 0;
        
        sum += get_max_sum_node(root -> left, max_sum_node);
        sum += root -> data;
        sum += get_max_sum_node(root -> right, max_sum_node);
        
        if(sum > max)
        {
            max = sum;
            *max_sum_node = root;
        }
        
        return sum;
    }
    return 0;
}

here is one good solution,

puddleofriddles.blogspot.com/2012/01/write-program-to-find-sub-tree-in.html

tree contains negative values?

Considering tree has got negative values else otherwise max will be the tree itself.

Define one HashMap<TreeNode,Integer> to store sum of node.This is to make sure we dont calculate the sum of one subtree more than once.

static int SumNode(TreeNode node){
int sum = 0;
if(node == null)
return 0;
else{
if(map.containsKey(node))
return map.get(node);
else{
sum = node.data + SumNode(node.left) + SumNode(node.right);
map.put(node,sum);
return sum;
}
}
}


static int MaxSum(TreeNode root){
if(root == null)
return 0;
else
return Math.max(SumNode(root),Math.max(MaxSum(root.left),MaxSum(root.right)));
}

What about just recursively traversing the tree while giving a pointer to pointer to Node and a reference to the max value?

Node* maxSubtree(Node* r) {
    int max = -oo;
    Node* maxNode = NULL;
    f(r, max, &maxNode);
    return maxNode;
}
int f(Node* r, int& max, Node** maxNode) {
    if(r==NULL) return 0;
    int sum = f(r->left, max, maxNode) + f(r->right, max, maxNode) + r->data;
    if(sum>max) {
        max = sum;
        *maxNode = r;
    }
    return sum;
}

If the root of subtree is smaller or equal to 0, then the summation of its left subtree must be negative, so its right subtree has the larger summation than it. This pattern should save at least half of computation.

Then we traverse down to its right subtree.

If the root is larger than 0, then add the summation of its left subtree and itself, if it is negative, it's the same to the previous situation so we recursively investigate its right subtree. Otherwise, this tree has the maximum summation.

Not quite sure, anyone find bugs?

@Manan: Your algorithm is brute force and its O(n^2) time and O(n) space.

public class TreeSum {
	public static class Node {
		int value;
		Node left;
		Node right;
		
		public Node(int value, Node left, Node right) {
			this.value = value;
			this.left = left;
			this.right = right;
		}
	}
	
	public static class Result{
		Node node;
		int max;
		int sum;
		
		public Result(Node node, int max, int sum) {
			this.node = node;
			this.max = max;
			this.sum = sum;
		}
	}
	
	public static Result findMaximum(Node root) {
		if (root == null) {
			return new Result(root, 0, 0);
		} else {
			Result left = findMaximum(root.left);
			Result right = findMaximum(root.right);
			int sum = left.sum + right.sum + root.value;
			int max = sum;
			Node node = root;
			if (max < left.max) {
				max = left.max;
				node = left.node;
			} 
			
			if (max < right.max) {
				max = right.max;
				node = right.node;
			}
			return new Result(node, max, sum);
		}
	}
}