C++ program to add all greater values to every node in a given binary search tree
Description:
This Program is to add all greater values to every node in a given binary search tree.
For Example:
Input :
The Elements are : 5 , 10 , 15 , 20 , 25
Output :
Elements entered : 75 70 60 45 25
Program :
//C++ program to add all greater values to every node in a given binary search tree
using namespace std;
// tree node
struct Node
{
int data;
Node *left, *right;
};
// returns a new tree Node
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// A function to create binary tree.
Node* Tree(Node* temp, int data )
{
// If the tree is empty, return a new node
if (temp == NULL)
return newNode(data);
// Otherwise, recur down the tree
if (data < temp->data)
temp->left = Tree(temp->left, data);
else
temp->right = Tree(temp->right, data);
//return the (unchanged) node pointer
return temp;
}
// Recursive function to add all greater values in every node
void modify(struct Node *root, int *add)
{
if (root == NULL) return;
// Recur for right subtree
modify(root->right, add);
// Now *sum has sum of nodes in right subtree, add root->data to sum and update root->data
*add = *add + root->data;
root->data = *add;
// Recur for left subtree
modify(root->left, add);
}
// A wrapper over modify
void modifyBST(struct Node *root)
{
int sum = 0;
modify(root, &sum);
}
//function to display all the element present in the binary tree
void display(struct Node* root)
{
if (root != NULL)
{
display(root->left);
cout<<root->data<<" ";
display(root->right);
}
}
int main()
{
int n,size;
Node *root = new Node;
root = NULL;
cout<<"Enter the size of array : ";
cin>>size;
int arr[size];
cout<<"Enter the elements in array : ";
for(int i=0;i<size;i++)
{
cin>>arr[i];
}
// Construct the binary tree.
for(int i = 0; i < size; i++)
{
root = Tree(root, arr[i]);
}
modifyBST(root);
cout<<"\nElements are : ";
display(root);
return 0;
}
Comments