# Transform a BST to greater sum tree

Here given code implementation process.

``````//C Program
//Transform a BST to greater sum tree
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
int data;
struct Node *left,*right;
};

//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
//Create a dynamic node of binary search tree
struct Node *new_node = (struct Node *)malloc(sizeof(struct Node ));

if(new_node!=NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL;//Initially node right-pointer is NULL

if(*root == NULL)
{
//When adds a first node in binary tree
*root = new_node;
}
else
{
struct Node *find = *root;
//iterate binary tree and add new node to proper position
while(find != NULL)
{
if(find -> data > data)
{
if(find->left==NULL)
{
find->left = new_node;
break;
}
else
{ //visit left sub-tree
find = find->left;
}
}
else
{
if(find->right == NULL)
{
find->right = new_node;
break;
}
else
{
//visit right sub-tree
find = find->right;
}
}
}
}
}else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}

}

//Convert BST to greater sum tree
int convert(struct Node*root,int *prev)
{
if(root != NULL)
{

convert(root->right,prev);

int temp=*prev;

*prev+=root->data;
//set new data value
root->data= temp;

convert(root->left,prev);

}
}
void inorder(struct Node*root)
{
if(root!=NULL)
{

inorder(root->left);
printf("%3d ",root->data );
inorder(root->right);
}
}
int main(){

struct Node*root = NULL;

//Add nodes in binary search tree
/*
5
/    \
3       8
/ \     / \
2   4   6   11
/            /
1            10

*/

inorder(root);
int prev=0;
convert(root,&prev);
/*
35
/     \
44      21
/ \     /   \
47  40  29    0
/             /
49            11
*/
printf("\n");
inorder(root);
return 0;
}``````

#### Output

``````  1   2   3   4   5   6   8  10  11
49  47  44  40  35  29  21  11   0 ``````
``````//C++ Program
//Transform a BST to greater sum tree
#include <iostream>
using namespace std;

//Structure of Binary Search Tree node
struct Node
{
int data;
Node *left,*right;
};

class BST
{

public:
Node*root;
BST();
//public methods
void inorder(Node*);
int convert(Node*,int *);
};
BST::BST()
{
root=NULL;
}
//Adding a new node in binary search tree
{
//Create a dynamic node of binary search tree
Node *new_node = new Node();

if(new_node!=NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL;//Initially node right-pointer is NULL

if(root == NULL)
{
//When adds a first node in binary tree
root = new_node;
}
else
{
Node *find = root;

//add new node to proper position
while(find != NULL)
{
if(find -> data >= data)
{
if(find->left==NULL)
{
find->left = new_node;
break;
}
else
{
//visit left sub-tree
find = find->left;
}
}
else
{
if(find->right == NULL)
{
find->right = new_node;
break;
}
else
{
//visit right sub-tree
find = find->right;
}
}
}
}
}
else
{
cout<<("Memory Overflow\n");
}
}
//Convert BST to greater sum tree
int BST :: convert(struct Node*root,int *prev)
{
if(root != NULL)
{

convert(root->right,prev);

int temp=*prev;

*prev+=root->data;
//set new data value
root->data= temp;

convert(root->left,prev);

}
}
void BST :: inorder(Node*root)
{
if(root!=NULL)
{

inorder(root->left);
cout<<"  "<< root->data;
inorder(root->right);
}
}

int main()
{
//Create object
BST obj;

//Add nodes in binary search tree
/*
5
/   \
3     8
/ \   / \
2   4  6  11
/          /
1          10
*/

obj.inorder(obj.root);
int prev=0;
obj.convert(obj.root,&prev);
/*
35
/   \
44    21
/ \    /  \
47 40  29   0
/           /
49          11
*/
cout<<("\n");
obj.inorder(obj.root);

return 0;
}``````

#### Output

``````  1  2  3  4  5  6  8  10  11
49  47  44  40  35  29  21  11  0``````
``````//Java program
//Transform a BST to greater sum tree
public class BST
{

static class Node
{
int data;
Node left,right;
}
public Node root;
public int prev;
//Class constructors
BST()
{
root=null;
prev=0;
}

//insert  element
{
//Create a dynamic node of binary search tree
Node new_node = new Node();

if(new_node != null)
{
//Set data and pointer values
new_node.data = data;
//Initially node left-pointer is null
new_node.left = null;
//Initially node right-pointer is null
new_node.right = null;

if(root == null)
{
//When adds a first node in binary tree
root = new_node;
}
else
{
Node find = root;

//add new node to proper position
while(find != null)
{
if(find.data >= data)
{
if(find.left==null)
{
find.left = new_node;
break;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if(find.right == null)
{
find.right = new_node;
break;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
System.out.println("Memory Overflow");
}
}
//Convert BST to greater sum tree
public void convert(Node root)
{
if(root != null)
{

convert(root.right);

int temp= prev;

prev+=root.data;
//set new data value
root.data= temp;

convert(root.left);

}
}
public void sum_tree()
{
prev=0;
convert(root);
}

public void inorder(Node root)
{
if(root!=null)
{

inorder(root.left);
System.out.print("  "+ root.data);
inorder(root.right);
}
}

public static void main(String[] args)
{

BST obj = new BST();

//Add nodes in binary search tree
/*
5
/   \
3     8
/ \   / \
2   4  6  11
/          /
1          10
*/

obj.inorder(obj.root);

obj.sum_tree();
/*
35
/   \
44    21
/ \    /  \
47 40  29   0
/           /
49          11
*/
System.out.println("\n");
obj.inorder(obj.root);

}
}``````

#### Output

``````  1  2  3  4  5  6  8  10  11

49  47  44  40  35  29  21  11  0``````
``````#Python Program
#Transform a BST to greater sum tree
class Node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None

class BST:

def __init__(self):

#Assign default value
self.root=None
self.prev=0

#insert  element

#Create a dynamic node of binary search tree
new_node = Node(data)

if(self.root == None):
#When adds a first node in binary tree
self.root = new_node

else:
find = self.root

#add new node to proper position
while(find != None):

if(find.data >= data):

if(find.left==None):

find.left = new_node
break

else:

#visit left sub-tree
find = find.left

else:

if(find.right == None):

find.right = new_node
break

else:

#visit right sub-tree
find = find.right

def inorder(self, root):

if(root!=None):

self.inorder(root.left)
print(root.data,end="  ")
self.inorder(root.right)

#Convert BST to greater sum tree
def  convert(self,root) :

if(root!= None) :

self.convert(root.right)
temp=self.prev
self.prev+= root.data
#set new data value
root.data= temp
self.convert(root.left)

def sum_tree(self) :

self.prev=0
self.convert(self.root)

def main():
obj = BST()

# Add nodes in binary search tree
#
#          5
#        /   \
#       3     8
#      /\    / \
#     2  4  6   11
#    /         /
#   1         10
#
obj.inorder(obj.root)

obj.sum_tree()
#
#         35
#        /   \
#       44    21
#      /  \   / \
#     47  40 29  0
#    /          /
#   49         11
#
print ("\n")
obj.inorder(obj.root)

if __name__ =="__main__":
main()``````

#### Output

``````1  2  3  4  5  6  8  10  11

49  47  44  40  35  29  21  11  0 ``````
``````//C# program
//Transform a BST to greater sum tree
using System;

public class Node
{
public int data;
public Node left,right;
}
public class BST
{

public Node root;
public int prev;
//Class constructors
BST()
{
root=null;
prev=0;
}

//insert  element
{
//Create a dynamic node of binary search tree
Node new_node = new Node();

if(new_node != null)
{
//Set data and pointer values
new_node.data = data;
//Initially node left-pointer is null
new_node.left = null;
//Initially node right-pointer is null
new_node.right = null;

if(root == null)
{
//When adds a first node in binary tree
root = new_node;
}
else
{
Node find = root;

//add new node to proper position
while(find != null)
{
if(find.data >= data)
{
if(find.left==null)
{
find.left = new_node;
break;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if(find.right == null)
{
find.right = new_node;
break;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
Console.WriteLine("Memory Overflow");
}
}
//Convert BST to greater sum tree
public void convert(Node root)
{
if(root != null)
{

convert(root.right);

int temp= prev;

prev+=root.data;
//set new data value
root.data= temp;

convert(root.left);

}
}
public void sum_tree()
{
prev=0;
convert(root);
}

public void inorder(Node root)
{
if(root!=null)
{

inorder(root.left);
Console.Write("  "+ root.data);
inorder(root.right);
}
}

public static void Main(String[] args)
{

BST obj = new BST();

//Add nodes in binary search tree
/*
5
/   \
3     8
/ \   / \
2   4  6  11
/          /
1          10
*/

obj.inorder(obj.root);

obj.sum_tree();
/*
35
/   \
44    21
/ \    /  \
47 40  29   0
/           /
49          11
*/
Console.WriteLine("\n");
obj.inorder(obj.root);

}
}``````

#### Output

``````  1  2  3  4  5  6  8  10  11

49  47  44  40  35  29  21  11  0
``````
``````<?php
//Php program
//Transform a BST to greater sum tree
class Node
{
public \$data;
public \$left;
public \$right;
function __construct(\$data)
{
\$this->data = \$data;
\$this->length = NULL;
\$this->right = NULL;
}
}
class BST
{

public \$root;
function __construct()
{
\$root=NULL;
}
//Adding a new node in binary search tree
{
//Create a dynamic node of binary search tree
\$new_node = new Node(\$data);

if(\$this->root == NULL)
{
//When adds a first node in binary tree
\$this->root = \$new_node;
}
else
{
\$find = \$this->root;

//add new node to proper position
while(\$find != NULL)
{
if(\$find->data >= \$data)
{
if(\$find->left==NULL)
{
\$find->left = \$new_node;
break;
}
else
{
//visit left sub-tree
\$find = \$find->left;
}
}
else
{
if(\$find->right == NULL)
{
\$find->right = \$new_node;
break;
}
else
{
//visit right sub-tree
\$find = \$find->right;
}
}
}
}

}

public function inorder(\$root)
{
if(\$root!=NULL)
{

\$this->inorder(\$root->left);
echo "  ". \$root->data;
\$this->inorder(\$root->right);
}
}

//Convert BST to greater sum tree
public function convert(\$root,&\$prev)
{
if(\$root!= NULL)
{

\$this->convert(\$root->right,\$prev);

\$temp=\$prev;

\$prev+= \$root->data;
//set new data value
\$root->data= \$temp;

\$this->convert(\$root->left,\$prev);

}
}

}
function main()
{
//Make a object of BST class
\$obj= new BST();

# Add nodes in binary search tree
#
#          5
#        /   \
#       3     8
#      /\    / \
#     2  4  6   11
#    /         /
#   1         10
#

\$obj->inorder(\$obj->root);
\$prev=0;
\$obj->convert(\$obj->root,\$prev);
#
#         35
#        /   \
#       44    21
#      /  \   / \
#     47  40 29  0
#    /          /
#   49         11
#
echo ("\n");
\$obj->inorder(\$obj->root);

}
main();
?>``````

#### Output

``````  1  2  3  4  5  6  8  10  11
49  47  44  40  35  29  21  11  0``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.