Duplicate removal in Binary Search Tree

#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;
}
Advertisements

2 thoughts on “Duplicate removal in Binary Search Tree

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s