Replace node with sum of left and right subtree

Given a Binary tree , Replace each node with sum of values in left and right subtree. leaf nodes value will be changed to 0.

Solution :

i) Traverse the tree recursively.
ii) Store the old value of the current node, recursively call for left and right subtrees and change the value of current node as sum of the values returned by the recursive calls.
iii) Return the sum of new value and old value.

struct node
{
  struct node *left;
  struct node *right;
  int value;
};
int SumTree(struct node* root)
{
	if(root==NULL)
	   return 0;
	int oldValue = root->value;
	
	int newValue = SumTree(root->left)+SumTree(root->right);	
	root->value = newValue;
	
	return newValue+oldValue;
}

Time Complexity : O(N)

One Thought on “Replace node with sum of left and right subtree

  1. Hey, if leaves are set to zero, then parent of leaf node will have sum = 0, so its value should be zero, and then its parent will have sum zero. Every node value just becomes zero. This question is misleading.

Leave a Reply to Titan Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation