Home » Interview coding problems/challenges

Transform to Sum Tree

In this article, we are going to see how to convert a binary tree to sum tree? This problem has been featured in Amazon, Microsoft. Submitted by Radib Kar, on December 24, 2018

Problem statement: Given a Binary Tree where each node has positive and negative values. Convert this to a tree where each node contains the sum of the left and right sub trees in the original tree. The values of leaf nodes are changed to 0.

Example

For example, the following tree
             10
           /    \
         -2      8
        /  \    / \
       6  -5  -7   5
Should be converted to:
          5(1-2-2+8)
          /        \
       1(6-5)    -2(-7+5)
       /   \       /  \
      0     0     0    0

Sum tree

A binary tree is said to be converted in sum tree:

1. All leaf nodes are converted to 0
2. All nodes have the sum of right subtree & left subtree in the original tree

Let's consider,

For any intermediate node having two child at k^th level

Value of the node must be updated as

Sum of right subtree of the node+ sum of left subtree of the node

Now consider both the right & left child has been already converted to their update node values having respective subtree sums up to (k+1)^th level (from bottom to (k+1)^th level).

So the node value should be updated as: right child value + left child value + subtree sums up to (k+1)^th level

=old right child value + old left child value + new left child value (sum of subtrees up to (k+1)^th level) + new right child value (sum of subtrees up to (k+1)^th level).

So, here we can develop our recursive function to develop the algo

FUNCTION toSumTree (node)
    1.  Check base case
        IF (node==NULL)
            Return 0;
    2.  Store old value of node
    3.  Update node value to left subtree sum + right 
        subtree sum. Use recursion to find subtree sums
    4.  Return old node value + current node value for 
        upper levels ( towards root)
END FUNCTION

C++ implementation for Transform to Sum Tree

#include <bits/stdc++.h>
using namespace std;

// tree node is defined
class tree{    
	public:
		int data;
		tree *left;
		tree *right;
};

//convert to sum tree
int toSumTree(tree *node){ 
	if(!node) //base case 
		return 0;
	
	//store old value
	int temp=node->data; 
	
	//update to new value
	node->data=toSumTree(node->left)+toSumTree(node->right); 
	
	//return for upper level sums
	return node->data+temp; 
}


//printing the tree using level order traversal
void printTree(tree* root){
	queue<tree*> q;  // using stl
	tree* temp;
	q.push(root);
	q.push(NULL);
	cout<<"root\n";
	while(!q.empty()){
		temp=q.front();
		q.pop();
		if(temp==NULL){
			if(!q.empty()){
				cout<<"\nnext level\n";
				q.push(NULL);
			}
		}
		else{
			cout<<temp->data<<" ";  //print node
			if(temp->left)
				q.push(temp->left); //EnQueue
			if(temp->right)
				q.push(temp->right); //EnQueue
		}
	}
}

// creating new node
tree* newnode(int data)  
{ 
	tree* node = (tree*)malloc(sizeof(tree)); 
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 
	return(node); 
} 


int main() 
{ 
	//**same tree is builted as shown in example**
	cout<<"same tree is built as shown in example\n";
	tree *root=newnode(10); 
	root->left= newnode(-2); 
	root->right= newnode(8); 
	root->right->right=newnode(5);
	root->right->left=newnode(-7);
	root->left->left=newnode(6); 
	root->left->right=newnode(-5);

	cout<<"printing the original tree...\n"; 
	printTree(root);

	toSumTree(root);
	cout<<"\nprinting the converted tree...\n";
	printTree(root);

	return 0; 
} 

Output

same tree is built as shown in example
printing the original tree...
root
10
next level
-2 8
next level
6 -5 -7 5
printing the converted tree...
root
5
next level
1 -2
next level
0 0 0 0

Explanation with example:

Let's see how the function solves the above example.

Original tree:
             10
           /    \
        -2       8
       /   \    /  \
     6    -5   -7    5
In the main function it calls toSumTree (10)
------------------------------------------------------------

toSumTree (10) //call at Main()
node is not NULL
temp=10
new node value = toSumTree (10->left) + toSumTree (10->right)
=toSumTree (-2) + toSumTree (8)
Thus call to toSumTree (-2) and toSumTree (8)
Return new node value + temp (10)
------------------------------------------------------------

toSumTree (-2) //call at toSumTree (10)
node is not NULL
temp=-2
new node value = toSumTree (-2->left) + toSumTree (-2->right)
=toSumTree (6) + toSumTree (-5)
Thus call to toSumTree (6) and toSumTree (-5)
Return new node value + temp (-2)
------------------------------------------------------------

toSumTree (8) //call at toSumTree (10)
node is not NULL
temp=8
new node value = toSumTree (8->left) + toSumTree (8->right)
=toSumTree (-7) + toSumTree (5)
Thus call to toSumTree (-7) and toSumTree (5)
Return new node value + temp (8)
------------------------------------------------------------

toSumTree (6) //call at toSumTree (-2)
node is not NULL
temp=6
new node value = toSumTree (6->left) + toSumTree (6->right)
=toSumTree (NULL) + toSumTree (NULL)
Thus call to toSumTree (NULL) and toSumTree (NULL)
Return new node value + temp (6)
------------------------------------------------------------

toSumTree (-5) //call at toSumTree (-2)
node is not NULL
temp=-5
new node value = toSumTree (-5->left) + toSumTree (-5->right)
=toSumTree (NULL) + toSumTree (NULL)
Thus call to toSumTree (NULL) and toSumTree (NULL)
Return new node value + temp (-5)
------------------------------------------------------------

toSumTree (-7)//call at toSumTree(8)
node is not NULL
temp=-7
new node value = toSumTree (-7->left) + toSumTree (-7->right)
=toSumTree (NULL) + toSumTree (NULL)
Thus call to toSumTree (NULL) and toSumTree (NULL)
Return new node value + temp (-7)
------------------------------------------------------------

toSumTree (5)//call at toSumTree (8)
node is not NULL
temp=5
new node value = toSumTree (5->left) + toSumTree (5->right)
=toSumTree (NULL) + toSumTree (NULL)
Thus call to toSumTree (NULL) and toSumTree (NULL)
Return new node value + temp (5)
------------------------------------------------------------

toSumTree (NULL)//call at toSumTree(6)
node is NULL
return 0
------------------------------------------------------------

toSumTree (NULL)//call at toSumTree (6)
node is NULL
return 0
------------------------------------------------------------

toSumTree (NULL)//call at toSumTree(-5)
node is NULL
return 0
------------------------------------------------------------

toSumTree (NULL)//call at toSumTree(-5)
node is NULL
return 0
------------------------------------------------------------

toSumTree (NULL)//call at toSumTree(-7)
node is NULL
return 0
------------------------------------------------------------

toSumTree (NULL)//call at toSumTree(-7)
node is NULL
return 0
------------------------------------------------------------

toSumTree (NULL)//call at toSumTree(5)
node is NULL
return 0
------------------------------------------------------------

toSumTree (NULL)//call at toSumTree(5)
node is NULL
return 0


At toSumTree (6) //call at toSumTree(-2)
new node value = toSumTree (6->left) + toSumTree (6->right)
=toSumTree (NULL) + toSumTree (NULL)
=0
6->0
It returns 0+6=6
------------------------------------------------------------

At toSumTree (-5) //call at toSumTree(-2)
new node value = toSumTree (-5->left) + toSumTree (-5->right)
=toSumTree (NULL) + toSumTree (NULL)
=0
-5->0
It returns 0-5=-5
------------------------------------------------------------

At toSumTree (-7) //call at toSumTree(8)
new node value = toSumTree (-7->left) + toSumTree (-7->right)
=toSumTree (NULL) + toSumTree (NULL)
=0
-7->0
It returns 0-7=-7
------------------------------------------------------------

At toSumTree (5) //call at toSumTree (8)
new node value = toSumTree (5->left) + toSumTree (5->right)
=toSumTree (NULL) + toSumTree (NULL)
=0
5->0
It returns 0+5=5
------------------------------------------------------------

At toSumTree (-2) //call at toSumTree(10)
new node value = toSumTree (-2->left) + toSumTree (-2->right)
=toSumTree (6) + toSumTree (-5)
=6 + (-5) =1
-2->1
It returns -2+1=-1
------------------------------------------------------------

At toSumTree (8) //call at toSumTree (10)
new node value = toSumTree (-8->left) + toSumTree (-8->right)
=toSumTree (-7) + toSumTree (5)
=-7 + (5) =-2
8->-2
It returns -2+8=6
------------------------------------------------------------

At toSumTree (10) //call at main
new node value = toSumTree (10->left) + toSumTree (10->right)
=toSumTree (-2) + toSumTree (8)
=-1 + 6=5
10->5
It returns 10+5=15

So, the binary tree is sum converted to:
             5
          /      \
         1        -2
       /   \      /   \
     0      0     0    0