Binary Trees: Convert Binary tree into Sum tree

Problem Statement:

You are given an binary tree, you need to convert into sum tree.

Example

Solution

We can solve this problem with the help of recursion.

Then we store the old value of the current node and recursively call for left and right sub tree and change the value of the current node as sum of the values.

Example:

Consider the below tree:

Pass 1:

node = 10
old_val = 10

As the node is not equal to NULL, store the node value in “old_val” and now we recursively call left and right sub tree.

Recursion Stack:

Now we will call the left sub tree “-2”

Pass 2:

node = -2
old_val = -2

Recursion stack:

Again we call for left sub tree, i.e “8”

Pass 3:

node = 8
old_val = 8

Next there are no left child for 8, it will point to NULL

Recursion stack

Pass 4 :

Since the node is NULL we return 0.

Since the right child of 8 is also NULL, we return 0.

Recursion stack

Tree:

Pass 5 :

node = 0
old_val = 8

Now we return the node data + old_val.

Since node data is 0 and old_val is 8, the result will be 8.

Similarly we go to the right child now and continue the execution to get to the result.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <unordered_map> 

using namespace std;
  
struct node 
{ 
      int data; 
      node *left; 
      node *right; 

    node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
}; 
  
int convert_to_sum_tree(node *Node) 
{ 
    if(Node == NULL) 
    return 0; 
  
    int old_val = Node->data; 
  
    Node->data = convert_to_sum_tree(Node->left) + convert_to_sum_tree(Node->right); 
  
    return Node->data + old_val; 
} 

void print_inorder(node* Node) 
{ 
    if (Node == NULL) 
        return; 
    print_inorder(Node->left); 
    cout<<" "<<Node->data; 
    print_inorder(Node->right); 
} 
  

int main() 
{ 
    node *root = NULL; 
      
    root = new node(10); 
    root->left = new node(-2); 
    root->right = new node(6); 
    root->left->left = new node(8); 
    root->left->right = new node(-4); 
    root->right->left = new node(7); 
    root->right->right = new node(5); 
      
    convert_to_sum_tree(root); 
      
    cout<<"Inorder Traversal of the tree is: \n"; 
    print_inorder(root); 
    return 0; 
} 

Output:

Inorder Traversal of the tree is:
0 4 0 20 0 12 0