Amazon SunGard Interview Question
Software Engineer / DevelopersTeam: Elastic Mapreduce
Country: United States
Interview Type: Phone Interview
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;
}
This is post order as you are calculating sum (& calc max update) at the end and not in btw.
Also consider a corner case where all nodes are -ve, your algo returns 0. You need to do (root->left != NULL) or checking max_sum_node value etc
I think you don't need max variable as you are anyway having **max_sum_node.
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)));
}
You are consuming O(n) space in form of hashmap just to ensure that you don't calculate sum of a sub-tree twice. You could to a pre-order traversal.
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;
}
Above code works just perfect. But I have a doubt if we have to always include the leaf node in the sub tree?
Can we have a sub tree without including the leaf nodes of the main tree.
If I understand your question, no. By definition of a tree, I think we need to include all the children (including leaves) of a given node if want to consider it as a tree.
@crdmp :
Shouldn't the code be:
Node* maxSubtree(Node* r) {
int max = -oo;
Node* maxNode = NULL;
f(r, &max, &maxNode);//Change
return maxNode;
}
int f(Node* r, int *max, Node** maxNode) {//Change
if(r==NULL) return 0;
int sum = f(r->left, max, maxNode) + f(r->right, max, maxNode) + r->data;
if(sum> *max) {//Change
*max = sum;//Change
*maxNode = r;
}
return sum;
}
Check the lines with the comment: "//Change"
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?
Running time is best case: lg(n)---only max node is positive; worse-cars: n/2, calculate summation of left subtree.
{If the root of subtree is smaller or equal to 0, then the summation of its left subtree must be negative}
Why is this? It could also be that the right subtree might be negative.E.g. Root is -4, left is 8 and right is 4.(A tree with 3 nodes).With your approach you say the right child is the max tree but it it has 4 < 8
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);
}
}
}
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)
- RamBabu December 31, 2011