Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Problem Statement
Sample Example
Steps of Algorithm
Implementation in C++
Complexity Analysis
Frequently Asked Questions
What is a binary Tree?
What is post order Traversal in binary tree?
What are different traversals possible in binary trees?
Last Updated: Mar 27, 2024

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

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


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



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.


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++

using namespace std;
//A Tree Node
class Node
    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)
    //calling the function for left subtree
    //calling the function for right subtree

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
    //Print the modified tree in Inorder fashion



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

Frequently Asked Questions

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.


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!!

Previous article
How to Remove Subtrees Containing Zeroes in a Binary Tree
Next article
Check Whether Every Node of the Binary Tree has a Value K on itself or its any Immediate Neighbours
Live masterclass