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.
For example, the following tree
10
/ \
-2 6
/ \ / \
8 -4 7 5
should be changed to
20(4-2+12+6)
/ \
4(8-4) 12(7+5)
/ \ / \
0 0 0 0
Solution:
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).
C++
// C++ program to convert a tree into its sum tree#include <bits/stdc++.h>using namespace std;/* A tree node structure */class node { public:int data; node *left; node *right; }; // Convert a given tree to a tree where // every node contains sum of values of // nodes in left and right subtrees in the original tree int toSumTree(node *Node) { // Base case if(Node == NULL) return 0; // Store the old value int old_val = Node->data; // Recursively call for left and // right subtrees and store the sum as // old value of this node Node->data = toSumTree(Node->left) + toSumTree(Node->right); // Return the sum of values of nodes // in left and right subtrees and // old_value of this node return Node->data + old_val; } // A utility function to print // inorder traversal of a Binary Tree void printInorder(node* Node) { if (Node == NULL) return; printInorder(Node->left); cout<<" "<<Node->data; printInorder(Node->right); } /* Utility function to create a new Binary Tree node */node* newNode(int data) { node *temp = new node; temp->data = data; temp->left = NULL; temp->right = NULL; return temp; } /* Driver code */int main() { node *root = NULL; int x; /* Constructing tree given in the above figure */ root = newNode(10); root->left = newNode(-2); root->right = newNode(6); root->left->left = newNode(8); root->left->right = newNode(-4); root->right->left = newNode(7); root->right->right = newNode(5); toSumTree(root); // Print inorder traversal of the converted // tree to test result of toSumTree() cout<<"Inorder Traversal of the resultant tree is: \n"; printInorder(root); return 0; } // This code is contributed by rathbhupendra |
C
#include<stdio.h>/* A tree node structure */struct node{ int data; struct node *left; struct node *right;};// Convert a given tree to a tree where every node contains sum of values of// nodes in left and right subtrees in the original treeint toSumTree(struct node *node){ // Base case if(node == NULL) return 0; // Store the old value int old_val = node->data; // Recursively call for left and right subtrees and store the sum as // new value of this node node->data = toSumTree(node->left) + toSumTree(node->right); // Return the sum of values of nodes in left and right subtrees and // old_value of this node return node->data + old_val;}// A utility function to print inorder traversal of a Binary Treevoid printInorder(struct node* node){ if (node == NULL) return; printInorder(node->left); printf("%d ", node->data); printInorder(node->right);}/* Utility function to create a new Binary Tree node */struct node* newNode(int data){ struct node *temp = new struct node; temp->data = data; temp->left = NULL; temp->right = NULL; return temp;}/* Driver function to test above functions */int main(){ struct node *root = NULL; int x; /* Constructing tree given in the above figure */ root = newNode(10); root->left = newNode(-2); root->right = newNode(6); root->left->left = newNode(8); root->left->right = newNode(-4); root->right->left = newNode(7); root->right->right = newNode(5); toSumTree(root); // Print inorder traversal of the converted tree to test result of toSumTree() printf("Inorder Traversal of the resultant tree is: \n"); printInorder(root); getchar(); return 0;} |
Java
// Java program to convert a tree into its sum tree // A binary tree nodeclass Node { int data; Node left, right; Node(int item) { data = item; left = right = null; }} class BinaryTree { Node root; // Convert a given tree to a tree where every node contains sum of // values of nodes in left and right subtrees in the original tree int toSumTree(Node node) { // Base case if (node == null) return 0; // Store the old value int old_val = node.data; // Recursively call for left and right subtrees and store the sum // as new value of this node node.data = toSumTree(node.left) + toSumTree(node.right); // Return the sum of values of nodes in left and right subtrees // and old_value of this node return node.data + old_val; } // A utility function to print inorder traversal of a Binary Tree void printInorder(Node node) { if (node == null) return; printInorder(node.left); System.out.print(node.data + " "); printInorder(node.right); } /* Driver function to test above functions */ public static void main(String args[]) { BinaryTree tree = new BinaryTree(); /* Constructing tree given in the above figure */ tree.root = new Node(10); tree.root.left = new Node(-2); tree.root.right = new Node(6); tree.root.left.left = new Node(8); tree.root.left.right = new Node(-4); tree.root.right.left = new Node(7); tree.root.right.right = new Node(5); tree.toSumTree(tree.root); // Print inorder traversal of the converted tree to test result // of toSumTree() System.out.println("Inorder Traversal of the resultant tree is:"); tree.printInorder(tree.root); }}// This code has been contributed by Mayank Jaiswal |
Python3
# Python3 program to convert a tree # into its sum tree # Node definition class node: def __init__(self, data): self.left = None self.right = None self.data = data # Convert a given tree to a tree where # every node contains sum of values of # nodes in left and right subtrees # in the original tree def toSumTree(Node) : # Base case if(Node == None) : return 0 # Store the old value old_val = Node.data # Recursively call for left and # right subtrees and store the sum as # new value of this node Node.data = toSumTree(Node.left) + \ toSumTree(Node.right) # Return the sum of values of nodes # in left and right subtrees and # old_value of this node return Node.data + old_val # A utility function to print # inorder traversal of a Binary Tree def printInorder(Node) : if (Node == None) : return printInorder(Node.left) print(Node.data, end = " ") printInorder(Node.right) # Utility function to create a new Binary Tree node def newNode(data) : temp = node(0) temp.data = data temp.left = None temp.right = None return temp # Driver Code if __name__ == "__main__": root = None x = 0 # Constructing tree given in the above figure root = newNode(10) root.left = newNode(-2) root.right = newNode(6) root.left.left = newNode(8) root.left.right = newNode(-4) root.right.left = newNode(7) root.right.right = newNode(5) toSumTree(root) # Print inorder traversal of the converted # tree to test result of toSumTree() print("Inorder Traversal of the resultant tree is: ") printInorder(root) # This code is contributed by Arnab Kundu |
C#
// C# program to convert a tree // into its sum tree using System;// A binary tree node public class Node{ public int data; public Node left, right; public Node(int item) { data = item; left = right = null; }}class GFG{public Node root;// Convert a given tree to a tree where // every node contains sum of values of // nodes in left and right subtrees in // the original tree public virtual int toSumTree(Node node){ // Base case if (node == null) { return 0; } // Store the old value int old_val = node.data; // Recursively call for left and // right subtrees and store the sum // as new value of this node node.data = toSumTree(node.left) + toSumTree(node.right); // Return the sum of values of nodes // in left and right subtrees old_value // of this node return node.data + old_val;}// A utility function to print// inorder traversal of a Binary Tree public virtual void printInorder(Node node){ if (node == null) { return; } printInorder(node.left); Console.Write(node.data + " "); printInorder(node.right);}// Driver Codepublic static void Main(string[] args){ GFG tree = new GFG(); /* Constructing tree given in the above figure */ tree.root = new Node(10); tree.root.left = new Node(-2); tree.root.right = new Node(6); tree.root.left.left = new Node(8); tree.root.left.right = new Node(-4); tree.root.right.left = new Node(7); tree.root.right.right = new Node(5); tree.toSumTree(tree.root); // Print inorder traversal of the // converted tree to test result of toSumTree() Console.WriteLine("Inorder Traversal of " + "the resultant tree is:"); tree.printInorder(tree.root);}}// This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript program to convert a tree // into its sum tree // A binary tree node class Node{ constructor(item) { this.data = item; this.left = null; this.right = null; }}var root = null;// Convert a given tree to a tree where // every node contains sum of values of // nodes in left and right subtrees in // the original tree function toSumTree(node){ // Base case if (node == null) { return 0; } // Store the old value var old_val = node.data; // Recursively call for left and // right subtrees and store the sum // as new value of this node node.data = toSumTree(node.left) + toSumTree(node.right); // Return the sum of values of nodes // in left and right subtrees old_value // of this node return node.data + old_val;}// A utility function to print// inorder traversal of a Binary Tree function printInorder(node){ if (node == null) { return; } printInorder(node.left); document.write(node.data + " "); printInorder(node.right);}// Driver Code/* Constructing tree given in the above figure */root = new Node(10);root.left = new Node(-2);root.right = new Node(6);root.left.left = new Node(8);root.left.right = new Node(-4);root.right.left = new Node(7);root.right.right = new Node(5);toSumTree(root);// Print inorder traversal of the // converted tree to test result of toSumTree() document.write("Inorder Traversal of " + "the resultant tree is:<br>");printInorder(root);</script> |
Output
Inorder Traversal of the resultant tree is: 0 4 0 20 0 12 0
Time Complexity: The solution involves a simple traversal of the given tree. So the time complexity is O(n) where n is the number of nodes in the given Binary Tree.
Auxiliary Space : O(1) since using constant variables
Using postorder concept:
The idea is to use post order concept and store the value of left and right subtree and return it accordingly.
Steps to solve:
1. check if the root node is not equal to null:
- declare l , r variable to recurse left and right.
- declare temp variable to store to value of root data.
- update the root data to l+r.
- return temp+l+r.
2. Else return 0.
Implementation of the approach:
C++
// C++ program to convert a tree into its sum tree#include <bits/stdc++.h>using namespace std;/* A tree node structure */class node {public: int data; node* left; node* right;};// Convert a given tree to a tree where// every node contains sum of values of// nodes in left and right subtrees in the original treeint toSumTree(node* Node){ //check for the base condition if (Node != NULL) { //recurse the left subtree int l = toSumTree(Node->left); //recurse the right subtree int r = toSumTree(Node->right); //storing the temp value of root value int temp = Node->data; //update the root node Node->data = l + r; //return the recurse value return temp + l + r; } else return 0;}// A utility function to print// inorder traversal of a Binary Treevoid printInorder(node* Node){ if (Node == NULL) return; printInorder(Node->left); cout << " " << Node->data; printInorder(Node->right);}/* Utility function to create a new Binary Tree node */node* newNode(int data){ node* temp = new node; temp->data = data; temp->left = NULL; temp->right = NULL; return temp;}/* Driver code */int main(){ node* root = NULL; int x; /* Constructing tree given in the above figure */ root = newNode(10); root->left = newNode(-2); root->right = newNode(6); root->left->left = newNode(8); root->left->right = newNode(-4); root->right->left = newNode(7); root->right->right = newNode(5); toSumTree(root); // Print inorder traversal of the converted // tree to test result of toSumTree() cout << "Inorder Traversal of the resultant tree is: \n"; printInorder(root); return 0;}// This code is contributed by Prateek Kumar Singh |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;// Define structure of your nodeclass Node { int data; Node left, right; Node(int item) { data = item; left = right = null; }} class GFG {//Convert a given tree to its Sum Treepublic static int toSumTree(Node root){ if (root != null) { // Traverse left subtree int l = toSumTree(root.left); // Traverse right subtree int r = toSumTree(root.right); //storing the root value in temp node int temp = root.data; // Now update the root node root.data = l + r; //return the recurse value return temp + l + r; } else return 0;} // Function to print inorder traversal of binary treepublic static void printInorder(Node root){ if (root == null) return; printInorder(root.left); System.out.println(root.data); printInorder(root.right);}// Function to create new binary tree public static Node newNode(int data){ Node temp = new Node(data); temp.data = data; temp.left = null; temp.right = null; return temp;} public static void main (String[] args) { Node root = null; int x; //Constructing tree given in the above figure root = newNode(10); root.left = newNode(-2); root.right = newNode(6); root.left.left = newNode(8); root.left.right = newNode(-4); root.right.left = newNode(7); root.right.right = newNode(5); // calling function to convert tree to sum tree toSumTree(root); // print inorder traversal of tree System.out.println("Inorder Traversal of the resultant tree is: \n"); printInorder(root); }} |
C#
// C# program to convert a tree into its sum treeusing System;using System.Collections.Generic;class GFG{ /* A tree node structure */ class node { public int data; public node left; public node right; public node(int data) { this.data=data; this.left=null; this.right=null; } } // Convert a given tree to a tree where // every node contains sum of values of // nodes in left and right subtrees in the original tree static int toSumTree(node Node) { //check for the base condition if (Node != null) { //recurse the left subtree int l = toSumTree(Node.left); //recurse the right subtree int r = toSumTree(Node.right); //storing the temp value of root value int temp = Node.data; //update the root node Node.data = l + r; //return the recurse value return temp + l + r; } else return 0; } // A utility function to print // inorder traversal of a Binary Tree static void printInorder(node Node) { if (Node == null) return; printInorder(Node.left); Console.Write(" " + Node.data); printInorder(Node.right); } /* Driver code */ static void Main(string[] args) { node root = null; int x; /* Constructing tree given in the above figure */ root = new node(10); root.left = new node(-2); root.right = new node(6);root.left.left = new node(8); root.left.right = new node(-4); root.right.left = new node(7); root.right.right = new node(5); toSumTree(root); // Print inorder traversal of the converted // tree to test result of toSumTree() Console.Write("Inorder Traversal of the resultant tree is: \n"); printInorder(root); }} |
Javascript
// JS program to convert a tree into its sum tree/* A tree node structure */class Node { constructor(data) { this.data = data; this.left = null; this.right = null; }};// Convert a given tree to a tree where// every node contains sum of values of// nodes in left and right subtrees in the original treefunction toSumTree( Node){ // check for the base condition if (Node != null) { // recurse the left subtree let l = toSumTree(Node.left); // recurse the right subtree let r = toSumTree(Node.right); // storing the temp value of root value let temp = Node.data; // update the root node Node.data = l + r; // return the recurse value return temp + l + r; } else return 0;}// A utility function to print// inorder traversal of a Binary Treefunction printInorder(Node){ if (Node == null) return; printInorder(Node.left); console.log(" " + Node.data); printInorder(Node.right);}/* Driver code */let x;/* Constructing tree given in the above figure */let root = new Node(10);root.left = new Node(-2);root.right = new Node(6);root.left.left = new Node(8);root.left.right = new Node(-4);root.right.left = new Node(7);root.right.right = new Node(5);toSumTree(root);// Print inorder traversal of the converted// tree to test result of toSumTree()console.log("Inorder Traversal of the resultant tree is: <br>");printInorder(root); |
Python3
# Python3 program to convert a tree# into its sum tree# Node definitionclass node: def __init__(self, data): self.left = None self.right = None self.data = data# Convert a given tree to a tree where# every node contains sum of values of# nodes in left and right subtrees# in the original treedef toSumTree(Node) : # Base case if(Node == None) : return 0 # Store the old value old_val = Node.data # Recursively call for left and # right subtrees and store the sum as # new value of this node Node.data = toSumTree(Node.left) + \ toSumTree(Node.right) # Return the sum of values of nodes # in left and right subtrees and # old_value of this node return Node.data + old_val# A utility function to print# inorder traversal of a Binary Treedef printInorder(Node) : if (Node == None) : return printInorder(Node.left) print(Node.data, end = " ") printInorder(Node.right) # Utility function to create a new Binary Tree nodedef newNode(data) : temp = node(0) temp.data = data temp.left = None temp.right = None return temp# Driver Codeif __name__ == "__main__": root = None x = 0 # Constructing tree given in the above figure root = newNode(10) root.left = newNode(-2) root.right = newNode(6) root.left.left = newNode(8) root.left.right = newNode(-4) root.right.left = newNode(7) root.right.right = newNode(5) toSumTree(root) # Print inorder traversal of the converted # tree to test result of toSumTree() print("Inorder Traversal of the resultant tree is: ") printInorder(root)# This code is contributed by Arnab Kundu |
Output
Inorder Traversal of the resultant tree is: 0 4 0 20 0 12 0
Time Complexity: O(n), where n is the number of nodes.
Auxiliary Space : O(1) since using constant variables
This approach is contributed by Prateek Kumar Singh (pkrsingh025).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
