Maximum Sum of the tree | CODING INTERVIEW ARCHIVES
Given a binary tree, where the value of each node is non-negative, you have to find the maximum sum which is formed using the nodes. But condition here is that, if you consider a node into your sum calculation then you can not take it's direct parent (if any) as well as it's direct children (if any).
Approach:
It may seem, at first, a problem of level-order traversal. But it's not. To counter that, let's take an example:
Read full article from Maximum Sum of the tree | CODING INTERVIEW ARCHIVES
Given a binary tree, where the value of each node is non-negative, you have to find the maximum sum which is formed using the nodes. But condition here is that, if you consider a node into your sum calculation then you can not take it's direct parent (if any) as well as it's direct children (if any).
Approach:
It may seem, at first, a problem of level-order traversal. But it's not. To counter that, let's take an example:
As it can be seen from the tree, maximum sum is formed using shaded nodes which is 26.
Actually, recursion works just fine here.
For any node:
Calculate sum of left sub-tree and right sub-tree.
Also, calculate sum of left sub-tree of left node, right sub-tree of left node, left sub-tree of right node, right sub-tree of right node and node's data.
Return maximum of two.
// use map to store sum to avoid recompute
int max_sum(struct node* root){
if(!root)
return 0;
int leftsum = 0,rightsum = 0;
int llsum = 0,lrsum = 0,rlsum = 0,rrsum = 0;
leftsum = max_sum(root->left);
rightsum = max_sum(root->right);
if(root->left){
llsum = max_sum(root->left->left);
lrsum = max_sum(root->left->right);
}
if(root->right){
rlsum = max_sum(root->right->left);
rrsum = max_sum(root->right->right);
}
int without_this = leftsum + rightsum;
int with_this = llsum + lrsum + rlsum + rrsum + root->data;
return max(without_this, with_this);
}
int max(int a, int b){
return (a > b) ? a : b;
}
