Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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

Author 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

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.

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

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