1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.3.
Complexity Analysis
3.
3.1.
What is a binary Tree?
3.2.
What is post order Traversal in binary tree?
3.3.
What are different traversals possible in binary trees?
4.
Conclusion
Last Updated: Mar 27, 2024

# Change a Binary Tree so that every node stores sum of all nodes in left subtree

Ankit kumar
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

## Introduction

In this blog, we will discuss the approach to converting each node in a binary tree to the sum of values of the left subtree nodes and the nodeâ€™s value itself. Before jumping on the approach to the problem, let us first understand the problem.

### Problem Statement

Given a binary tree of integers, you have to change the value of each nodeâ€™s value to the sum of values of the left subtree nodes and the nodeâ€™s value itself and, finally, print the modified binary tree.

### Sample Example

Input:

Output:

Since 26 comes out as a sum of 8+(-4)+9+5. Similarly, 17 comes out as a sum of 8+9. No change in rootâ€™s right subtree because the left subtree of rootâ€™s right is NULL.

## Approach

The idea behind this approach is to do the postorder Traversal of the tree and compute the left and right subtreeâ€™s sum value. After getting the value, change the nodeâ€™s value to the sum of the left and current nodeâ€™s values and finally return the sum of left and right subtrees along with the value of current nodeâ€™s value.

### Steps of Algorithm

Step 1: Create a function that will traverse the tree in a postorder fashion with the return type as an integer.

Step 2: Store the value of the sum of left and right subtree nodes in separate variables.

Step 3:  Change the current nodeâ€™s value as the sum of the current nodeâ€™s value and value of the left subtree sum.

Step 4: return the sum of left subtree, right subtree, and current node values.

Step 5: Print the modified tree.

### Implementation in C++

``````#include<bits/stdc++.h>
using namespace std;
//A Tree Node
class Node
{
public:
int val;
Node* left, *right;

Node(int val)
{
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
//function to modify the binary tree so that each node gets converted to the sum of the left subtree's value and the value itself.
int modifyTree(Node* root){
//base cases
if(root == NULL)
return 0;

if(root->left == NULL && root->right == NULL)
return root->val;
//calling for the left and right subtree
int leftTreeSum = modifyTree(root->left);
int rightTreeSum = modifyTree(root->right);
//modifying the root's value
root->val = root->val + leftTreeSum;
//returning the total sum
return root->val + rightTreeSum;
}

void printTree(Node* root){
//base case
if(root == NULL)
return;
//calling the function for left subtree
printTree(root->left);
cout<<root->val<<endl;
//calling the function for right subtree
printTree(root->right);
}

int main(){
//constructing the tree as in sample Example
struct Node* root = new Node(5);
root->left = new Node(9);
root->right = new Node(3);
root->left->left = new Node(8);
root->left->right = new Node(-4);
root->right->right = new Node(2);

//Calling the function to modify the tree
modifyTree(root);
//Print the modified tree in Inorder fashion
printTree(root);
}``````

Output:

``8  17  -4  26  3  2``

### Complexity Analysis

Time Complexity: O(n)

Since this approach is based on postorder traversal and postorder traversal costs O(n) time, therefore overall time complexity of this algorithm is O(n)

Space Complexity: O(1)

As no extra space is required apart from the given space, therefore space complexity would be of order O(1).

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

### What is a binary Tree?

A binary tree is a tree data structure that can have at most two child nodes which are referred to as left child and right child.

### What is post order Traversal in binary tree?

Post order Traversal is one of the tree traversing techniques used for visiting the nodes in the tree. The order of Traversal in post-order traversal is left child- right child - node. That means the left child node is visited first, then right child, and then the parent node.

### What are different traversals possible in binary trees?

There are different traversals possible in a binary tree. Some popular traversals are preorder traversal, postorder Traversal, inorder Traversal, and level order Traversal.

## Conclusion

This article discussed the approach to converting the binary tree to the sum of the left subtreeâ€™s value and the nodeâ€™s value itself. A postorder traversal-based solution is discussed with a time complexity of O(n).

Recommended problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Live masterclass