Replace node with sum of left and right subtree

Replace node with sum of left and right subtree

Today’s problem is to replace node with sum of left and right subtree below node. By sum of children, we mean sum of all children of node and not just it’s immediate left and right child.
For example, consider binary search tree below,
replace node with sum of left and right subtree

Output should be as

replace node with sum of children
Replaced nodes. Resultant tree

Do you see the pattern here? What should be done before we process a parent node? Yes, we must process it’s left and right child first. And that’s post order traversal of tree. All we need to do is to replace print statement with addition of two nodes. Also, make sure we return sum of left, right and node itself, as parent node of current node will require that.

Algorithm to replace node with sum of left and right subtree

1. Start with root node. 
2. If root is null return zero. 
3. If there is left child, replace left child with sum of its children. 
4. If there is right child, replace right child with sum of its children. 
5. Replace root with sum of its right and left child.
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
int replaceNodeWithSumOfChildren(Node *root){
	if (!root)
		return 0;
	int leftSum =  replaceNodeWithSumOfChildren(root->left);
	int rightSum = replaceNodeWithSumOfChildren(root->right);
 
	if(leftSum + rightSum != 0){
		root->value = leftSum + rightSum;
	}
	return root->value;
}
 
void inorderTraversal(Node * root){
	if(!root)
		return;
 
	inorderTraversal(root->left);
	printf("%d ", root->value);
	inorderTraversal(root->right);
}
Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
 
	return newNode;
}
Node *addNode(Node *node, int value){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}
 
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
 
	replaceNodeWithSumOfChildren(root);
 
	inorderTraversal(root);	
	return 0;
}

This implementation of replacing node with sum of left and right subtree requires to visit every node of the tree, hence complexity of algorithm is O(N).

Please share if there is something is wrong or missing. If you are interested in contributing to website or have an interview experience to share, please contact us and you can earn money too.