Change a Binary Tree so that every node stores sum of all nodes in left subtree
Given a Binary Tree, change the value in each node to sum of all the values in the nodes in the left subtree including its own.
Examples:
Input : 1 / \ 2 3 Output : 3 / \ 2 3 Input 1 / \ 2 3 / \ \ 4 5 6 Output: 12 / \ 6 3 / \ \ 4 5 6
We strongly recommend you to minimize your browser and try this yourself first.
The idea is to traverse the given tree in bottom up manner. For every node, recursively compute sum of nodes in left and right subtrees. Add sum of nodes in left subtree to current node and return sum of nodes under current subtree.
Below is the implementation of above idea.
C++
// C++ program to store sum of nodes // in left subtree in every node #include<bits/stdc++.h> using namespace std; // A tree node class node { public : int data; node* left, *right; /* Constructor that allocates a new node with the given data and NULL left and right pointers. */ node( int data) { this ->data = data; this ->left = NULL; this ->right = NULL; } }; // Function to modify a Binary Tree // so that every node stores sum of // values in its left child including // its own value int updatetree(node *root) { // Base cases if (!root) return 0; if (root->left == NULL && root->right == NULL) return root->data; // Update left and right subtrees int leftsum = updatetree(root->left); int rightsum = updatetree(root->right); // Add leftsum to current node root->data += leftsum; // Return sum of values under root return root->data + rightsum; } // Utility function to do inorder traversal void inorder(node* node) { if (node == NULL) return ; inorder(node->left); cout<<node->data<< " " ; inorder(node->right); } // Driver code int main() { /* Let us construct below tree 1 / \ 2 3 / \ \ 4 5 6 */ struct node *root = new node(1); root->left = new node(2); root->right = new node(3); root->left->left = new node(4); root->left->right = new node(5); root->right->right = new node(6); updatetree(root); cout << "Inorder traversal of the modified tree is: \n" ; inorder(root); return 0; } // This code is contributed by rathbhupendra |
C
// C program to store sum of nodes in left subtree in every // node #include<bits/stdc++.h> using namespace std; // A tree node struct node { int data; struct node* left, *right; }; // Function to modify a Binary Tree so that every node // stores sum of values in its left child including its // own value int updatetree(node *root) { // Base cases if (!root) return 0; if (root->left == NULL && root->right == NULL) return root->data; // Update left and right subtrees int leftsum = updatetree(root->left); int rightsum = updatetree(root->right); // Add leftsum to current node root->data += leftsum; // Return sum of values under root return root->data + rightsum; } // Utility function to do inorder traversal void inorder( struct node* node) { if (node == NULL) return ; inorder(node->left); printf ( "%d " , node->data); inorder(node->right); } // Utility function to create a new node struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } // Driver program int main() { /* Let us construct below tree 1 / \ 2 3 / \ \ 4 5 6 */ struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->right = newNode(6); updatetree(root); cout << "Inorder traversal of the modified tree is \n" ; inorder(root); return 0; } |
Java
// Java program to store sum of nodes in left subtree in every // node class GfG { // A tree node static class node { int data; node left, right; } // Function to modify a Binary Tree so that every node // stores sum of values in its left child including its // own value static int updatetree(node root) { // Base cases if (root == null ) return 0 ; if (root.left == null && root.right == null ) return root.data; // Update left and right subtrees int leftsum = updatetree(root.left); int rightsum = updatetree(root.right); // Add leftsum to current node root.data += leftsum; // Return sum of values under root return root.data + rightsum; } // Utility function to do inorder traversal static void inorder(node node) { if (node == null ) return ; inorder(node.left); System.out.print(node.data + " " ); inorder(node.right); } // Utility function to create a new node static node newNode( int data) { node node = new node(); node.data = data; node.left = null ; node.right = null ; return (node); } // Driver program public static void main(String[] args) { /* Let us construct below tree 1 / \ 2 3 / \ \ 4 5 6 */ node root = newNode( 1 ); root.left = newNode( 2 ); root.right = newNode( 3 ); root.left.left = newNode( 4 ); root.left.right = newNode( 5 ); root.right.right = newNode( 6 ); updatetree(root); System.out.println( "Inorder traversal of the modified tree is" ); inorder(root); } } |
Python3
# Python3 program to store sum of nodes # in left subtree in every node # Binary Tree Node # utility that allocates a new Node # with the given key class newNode: # Construct to create a new node def __init__( self , key): self .data = key self .left = None self .right = None # Function to modify a Binary Tree so # that every node stores sum of values # in its left child including its own value def updatetree(root): # Base cases if ( not root): return 0 if (root.left = = None and root.right = = None ) : return root.data # Update left and right subtrees leftsum = updatetree(root.left) rightsum = updatetree(root.right) # Add leftsum to current node root.data + = leftsum # Return sum of values under root return root.data + rightsum # Utility function to do inorder traversal def inorder(node) : if (node = = None ) : return inorder(node.left) print (node.data, end = " " ) inorder(node.right) # Driver Code if __name__ = = '__main__' : """ Let us construct below tree 1 / \ 2 3 / \ \ 4 5 6 """ root = newNode( 1 ) root.left = newNode( 2 ) root.right = newNode( 3 ) root.left.left = newNode( 4 ) root.left.right = newNode( 5 ) root.right.right = newNode( 6 ) updatetree(root) print ( "Inorder traversal of the modified tree is" ) inorder(root) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10) |
C#
// C# program to store sum of nodes in left // subtree in every node using System; class GfG { // A tree node class node { public int data; public node left, right; } // Function to modify a Binary Tree so // that every node stores sum of values // in its left child including its own value static int updatetree(node root) { // Base cases if (root == null ) return 0; if (root.left == null && root.right == null ) return root.data; // Update left and right subtrees int leftsum = updatetree(root.left); int rightsum = updatetree(root.right); // Add leftsum to current node root.data += leftsum; // Return sum of values under root return root.data + rightsum; } // Utility function to do inorder traversal static void inorder(node node) { if (node == null ) return ; inorder(node.left); Console.Write(node.data + " " ); inorder(node.right); } // Utility function to create a new node static node newNode( int data) { node node = new node(); node.data = data; node.left = null ; node.right = null ; return (node); } // Driver code public static void Main() { /* Let us construct below tree 1 / \ 2 3 / \ \ 4 5 6 */ node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.right = newNode(6); updatetree(root); Console.WriteLine( "Inorder traversal of the modified tree is" ); inorder(root); } } /* This code is contributed by Rajput-Ji*/ |
Javascript
<script> // Javascript program to store sum of nodes in left // subtree in every node // A tree node class node { constructor() { this .data = 0; this .left = null ; this .right = null ; } } // Function to modify a Binary Tree so // that every node stores sum of values // in its left child including its own value function updatetree(root) { // Base cases if (root == null ) return 0; if (root.left == null && root.right == null ) return root.data; // Update left and right subtrees var leftsum = updatetree(root.left); var rightsum = updatetree(root.right); // Add leftsum to current node root.data += leftsum; // Return sum of values under root return root.data + rightsum; } // Utility function to do inorder traversal function inorder(node) { if (node == null ) return ; inorder(node.left); document.write(node.data + " " ); inorder(node.right); } // Utility function to create a new node function newNode(data) { var nod = new node(); nod.data = data; nod.left = null ; nod.right = null ; return (nod); } // Driver code /* Let us construct below tree 1 / \ 2 3 / \ \ 4 5 6 */ var root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.right = newNode(6); updatetree(root); document.write( "Inorder traversal of the modified tree is<br>" ); inorder(root); // This code is contributed by rrrtnx. </script> |
Output
Inorder traversal of the modified tree is: 4 6 5 12 3 6
Time Complexity: O(n)
Auxiliary space: O(n) for implicit call stack as using recursion
Thanks to Gaurav Ahrirwar for suggesting this solution.
Contact Us