#include <stdio.h\>
class BinarySearchTree
{
private:
int data;
BinarySearchTree \*left, \*right;
public:
BinarySearchTree(const int d):data(d), left(NULL), right(NULL){}
~BinarySearchTree()
{
if(left !\= NULL)
{
delete left;
}
if(right !\= NULL)
{
delete right;
}
}
//remove duplicates
void removeDup()
{
if(left)
{
left\-\>removeDup();
left\-\>remove(data, this);
}
if(right)
right\-\>removeDup();
}
void remove(int value, BinarySearchTree \*parent)
{
if(value < data && left)
{
left\-\>remove(value, this);
}
else if(value \> data && right)
{
right\-\>remove(value, this);
}
else
remove(parent);
}
void remove(BinarySearchTree \*parent) //remove this node
{
if(left \=\= NULL && right \=\= NULL) //leaf
{
((parent\-\>left \=\= this) ? parent\-\>left :
parent->right) = NULL;
}
else
{
if (left != NULL && right != NULL) //two child
{
right->removeMin(this);
return;
}
else //one child
{
((parent->left == this) ? parent->left :
parent\-\>right) \= (left !\= NULL) ? left : right;
}
}
delete this;
}
void removeMin(BinarySearchTree \*root)
{
BinarySearchTree \*p \= this, \*parent \= root;
while(p\-\>left)
{
parent \= p;
p \= p\-\>left;
}
root\-\>data \= p\-\>data;
p\-\>remove(parent); //remove p
}
//constructs bst from an array
void construct(const int a\[\], const int n, const int i)
{
int j;
for(j\= i; j < n; ++j)
{
insert(a\[j\]);
}
}
void inorder() const
{
if(left)
left\-\>inorder();
printf("%d ", data);
if(right)
right\-\>inorder();
}
void insert(const int el)
{
if(el <\= data) //same element insert in left
{
if(left)
left\-\>insert(el);
else
{
left \= new BinarySearchTree(el);
}
}
else
{
if(right)
right\-\>insert(el);
else
{
right \= new BinarySearchTree(el);
}
}
}
};
int main()
{
int n;
scanf("%d", &n);
int i;
int a\[n\];
for(i \= 0; i <n; ++i)
scanf("%d", a + i);
BinarySearchTree \*t \= new BinarySearchTree(a\[0\]);
t\-\>construct(a, n, 1);
BinarySearchTree \*prev \= NULL;
t\-\>inorder();
printf("\\n");
t\-\>removeDup();
t\-\>inorder();
printf("\\n");
return 0;
}
```