# 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  ` `#include ` `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<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: "````;  ` `    ``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 ` `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 "````; ` `    ``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 con 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*/`

Output:

```Inorder traversal of the modified tree is
4 6 5 12 3 6```

Time Complexity: O(n)

Thanks to Gaurav Ahrirwar for suggesting this solution.

Tree Tree