Convert a given tree to its Sum Tree

Introduction

In this blog, we will be discussing the problem of given a Binary Tree with positive and negative values at each node. Convert this to a tree with each node containing the sum of the original Tree's left and right subtrees. The values of the leaf nodes are set to zero. 

Problem Statement

The problem above states that given a Binary Tree with positive and negative values at each node. Convert this to a tree with each node containing the sum of the original Tree's left and right subtrees. The values of the leaf nodes are set to zero.  

Sample Example

Example: Given the below binary tree, we need to convert this binary tree into a tree where the value of a node equals to sum of the nodes in the left and right subtrees including it's own value.

Output:

Approach

Do a traversal of the given tree. In the traversal, 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. Finally return the sum of new value and value (which is sum of values in the subtree rooted with this node).

To solve the above problem, we use the recursive approach of Binary tree traversal. Below is the solution:

1. Traverse the Tree you've been given. 
2. During the traverse, save the current node's previous value, recursively call for left and right subtrees, and set the current node's value to the total of the values returned by the recursive calls. 
3. Finally, add a new value and value and return the total (which is the sum of values in the subtree rooted with this node).

Pseudocode

traverse(root):
if root == leaf:
return 0
value = root->value
root->value = traverse(root->left) + traverse(root->right)
return value + root->value 

Implementation in C++

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

// Class for defining a Tree Node;
class Node{
    public:
    int value;
    Node* left;
    Node* right;
};

// Function to construct a new Node;
Node* NewNode(int val){
    Node* node = new Node;
    node->value = val;
    node->left = NULL;
    node->right = NULL;

    return node;
}

//To check if a leaf node;
bool leaf(Node* root){
    return(!root->left && !root->right);
}


//Function which constructs the Sum Tree;
int SumTree(Node* root){

    //If leaf node, the we simply put 0 in that node and returns
    if(leaf(root)){
        int old_ = root->value;
        //Storing value of 0 in leaf node;
        root->value = 0;
       
        //returns the old value;
        return old_ + root->value;
    }

    //Storing the old value;
    int old_ = root->value;
    //Storing the value of sum of left + right subtree;
    root->value = SumTree(root->left) + SumTree(root->right);
    //returning the sum of old value and new root value;
    return old_ + root->value;
}

//Function of Inorder traversal;
void Inorder(Node* root){
    if(!root){
        return;
    }
    Inorder(root->left);
    cout<<root->value<<" ";
    Inorder(root->right);
}
void solve()
{  
    Node* root = NewNode(1);
    root->left = NewNode(2);
    root->right = NewNode(3);
    root->left->left = NewNode(3);
    root->left->right = NewNode(2);
    root->right->left = NewNode(-3);
    root->right->right = NewNode(-2);
   
    cout<<"Normal Tree: ";
    Inorder(root);
    cout<<'\n';
    SumTree(root);
    cout<<"Sum Tree: ";
    Inorder(root);
}  
int main()
{
    solve();
    return 0;
}

Output:

Normal Tree: 2 2 3 1 -2 3 -3 
Sum Tree: 0 5 0 5 0 -5 0 

Implementation in Python

#Class for defining a Node for 
#for the binary tree.
class Node:

def __init__(self, value):
	self.left = None
	self.right = None
	self.value = value


def SumTree(Node) :

	if(Node == None) :
		return 0
	# Storing the old value
	old_ = Node.value
    #Updating the value of Node with left and Right value;
	Node.value = SumTree(Node.left) + \
				SumTree(Node.right)
	# Returing the old vaue and new Node value
	return Node.value + old_

# Funtion for printing the Inorder traversal.
def Inorder(Node) :
	if Node == None :
		return
	Inorder(Node.left)
	print(Node.value, end = " ")
	Inorder(Node.right)

# Function for defining a New node of the tree;
def Newnode(value) :
	node = Node(0)
	node.value = value
	node.left = None
	node.right = None
	
	return node

if __name__ == "__main__":
	root = None

	root = Newnode(1)
	root.left = Newnode(2)
	root.right = Newnode(3)
	root.left.left = Newnode(2)
	root.left.right = Newnode(3)
	root.right.left = Newnode(-2)
	root.right.right = Newnode(-3)

	print("Normal Tree: ")
	Inorder(root)
	print("\n")
	SumTree(root)
	print("Sum Tree: ")
	Inorder(root)

Output:

Normal Tree: 2 2 3 1 -2 3 -3 
Sum Tree: 0 5 0 5 0 -5 0 

Complexity Analysis

Time complexity: O(n)

Explanation:

As in the above approach, we traverse each node of the Tree only once. Therefore, the Time Complexity of the Tree is O(n). 

Space complexity: O(log(n))

Explanation:

In the above approach, the space complexity is due to the recursive function. The maximum depth of the recursive call for the above function is equivalent to the Tree's height. For a binary tree, it is log(n), where n is the number of nodes in a tree. 

Therefore, the worst-case Space complexity is O(log(n)). 

Check out this problem - Diameter Of Binary Tree