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

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);
}

You can also try this code with Online C++ Compiler

Run Code

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