# C++ program to change a Binary Tree so that every node stores sum of all nodes in left subtree

Update every node of a binary tree such that it stores the sum of all nodes in its left subtree including its own in C++.

### What is a Binary Tree?

A non- linear data structure in which a node has at most 2 children which are its left child and its right child makes a binary tree.

### The approach towards the problem:

The approach to the problem is to find the sum of nodes in the left and right subtree with the help of recursion. Then add the sum of the left subtree to the present node and return the sum of nodes under the present tree.

## Examples:

```Input:
1
/    \
3       5
/  \     /
7     9   11

Output:  7 10 9 20 11 16

20                 1-> 1+3+7=20
/   \
10    16             3-> 3+7=10    5-> 5+11=16
/ \   /
7   9  11

Input:     5
/ \
6   7

Output: 6 11 7

11                5-> 5+6=11
/  \
6    7```

## Program to change a Binary tree so that every node stores sum all nodes in left subtree in C++

We will make a function sum that would update the binary tree such that every node stores sum of all nodes in the left subtree with the help of recursion. Let us see it with the help of the code below.

```#include<bits/stdc++.h>
using namespace std;

//creation of tree
class node
{
public:
int value;
node* left;
node* right;

//makes a new node with given value and left amn
// right pointers to NULL
node(int value)
{
this->value=value;
this->left=NULL;
this->right=NULL;
}
};

//to update the binary tree
//i.e. every node stores sum of all values of
//its left subtree
int sum_value(node *p)
{
if(p==NULL) return 0;

if(p->left==NULL && p->right==NULL) return p->value;

//for sum of left subtree
int left_subtree_sum=sum_value(p->left);

//for sum of right subtree
int right_subtree_sum=sum_value(p->right);

//add sum of left subtree to present node
p->value+=left_subtree_sum;
return p->value+right_subtree_sum;
}

//inorder traversal
void inorder_traversal(node *node)
{
if(node==NULL) return;
inorder_traversal(node->left);
cout<<node->value<<" ";
inorder_traversal(node->right);
}
int main()
{
node *p=new node(1);
p->left = new node(3);
p->right = new node(5);
p->left->left = new node(7);
p->left->right = new node(9);
p->right->left = new node(11);
sum_value(p);
cout<<"Inorder traversal of the resultant tree is: ";
inorder_traversal(p);
}

```

Output:

```Inorder traversal of the resultant tree: 7 10 9 20 11 16

```