Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.3.
Implementation in Python
2.4.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is Inorder Traversal?
3.2.
What is the Time Complexity of Inorder Traversal?
3.3.
What is the difference between Inorder, Preorder and Postorder Traversal?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Convert a given tree to its Sum Tree

Author Akshit Mehra
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is Inorder Traversal?

In order, Traversal is the Traversal of a binary tree in which we first visit the left node, then the current node, and then we visit the right node. Below is the traversal algorithm:

Algorithm Inorder (tree)

  1. Call in in Inorder to traverse the left subtree (left-subtree)
  2. Go to the root Node.
  3. Navigate to the appropriate subtree, i.e., call Inorder (right-subtree)

What is the Time Complexity of Inorder Traversal?

As we can see in the above algorithm, we see that we visit every node of the Tree only once. Therefore, the time complexity of the Inorder Traversal is O(n), where n is the number of nodes in the Tree.

What is the difference between Inorder, Preorder and Postorder Traversal?

  1. In order, you travel from the left subtree to the root, then to the right subtree.
  2. You go from the root to the left subtree, then to the right subtree for Preorder.
  3. You go from the left subtree to the right subtree, then to the root, in Post order.

Conclusion

This article discusses the problem of converting a given binary tree to its corresponding sum tree. Once you complete this, you may check out our Interview Preparation Course to level up your programming journey and get placed at your dream company. 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview bundle and interview experiences for placement preparations.

We hope this blog has helped you increase your knowledge regarding such DSA problems, and if you liked this blog, check other links. Do upvote our blog to help other ninjas grow. Happy Coding!"

Previous article
Convert an arbitrary Binary Tree to one that holds the Children Sum Property in its nodes
Next article
Maximum Width of a Binary Tree with a Null Value
Live masterclass