Forming sum tree of a givn tree (nodes are to be replaced with the sum of values of their children)

INPUT:-

OUTPUT:-

Good  question  to  pratice  recursion  and  asked  in  many  interviews  to  check  the  concepts  of  recursion  and  trees.  

Here  is  a  C++  code  for  this

#include<iostream.h>

using namespace std;

struct node

{

    int info;

    struct node* left;

    struct node* right;

};

node* newNode(int data)

{

    struct node* temp = new node;

    temp->info = data;

    temp->left = NULL;

    temp->right = NULL;

  return (temp);

}

int sumTree(node* root)

{

if(root==NULL)

return 0;

int sum=root->info;

root->info=sumTree(root->left) + sumTree(root->right);

return root->info+sum;

}

void preorder(node* root)

{

if(root==NULL)

return;

cout<<root->info<<"        ";

preorder(root->left);

preorder(root->right);

}

int main()

{

struct node *n1 = newNode(1);

    n1->left        = newNode(2);

    n1->right       = newNode(3);

    n1->left->left  = newNode(4);

    n1->left->right = newNode(5);

    n1->right->left  = newNode(6);

    n1->left->right->left = newNode(7);

    n1->left->right->right = newNode(8);

    preorder(n1);

    cout<<endl;

    sumTree(n1);

    preorder(n1);

    

return 0;

}