C++ program to replace every element with the least greater element on its right
Description:
This Program is to replace every element with the least greater element on its right of binary search tree.If the element is found it will replace it with the least greater element otherwise it will replace it by -1.
For Example:
Input :
The Elements are : 5 , 55 , 60 , 12 , 24
Output :
Elements entered : 12 60 -1 24 -1 (after replace every element with the least greater element on its right)
Program :
//C++ program to replace every element with the least greater element on its right
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 search tree and find successor.
void Tree(Node*& temp, int data ,Node*& succ )
{
// If the tree is empty, return a new node
if (temp == NULL)
temp = newNode(data);
// Otherwise, recur down the tree
if (data < temp->data)
{
succ = temp;
Tree(temp->left, data, succ);
}
else
if (data > temp->data)
Tree(temp->right, data, succ);
}
// Function to replace every element with the least greater element on its right
void replace(int arr[], int n)
{
Node* temp = NULL;
// start from right to left
for (int i = n - 1; i >= 0; i--)
{
Node* succ = NULL;
// insert current element into BST and find its inorder successor
Tree(temp, arr[i], succ);
// replace element by its inorder successor in BST
if (succ)
arr[i] = succ->data;
else //if no inorder successor is found
arr[i] = -1;
}
}
int main()
{
int n=0,size;
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];
}
n = sizeof(arr)/sizeof(arr[0]);
cout<<"\nElement are : ";
replace(arr, n);
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
Comments