# Remove duplicates in a Binary Search Tree

By | April 17, 2016

# Remove duplicate nodes in a Binary Search Tree (BST).

### Problem statement to remove redundant nodes in a Binary Search Tree.

Given a binary search tree (BST), remove the redundant nodes to obtain a tree without the duplicate elements.

### Example:

`INPUT: array: 1,5,8,10,10,12,15,20,20,20`
```OUTUT:
10(2)
/     \
5      15
/  \    /  \
1   8   12   20(3)
```

### Algorithm to remove duplicates :-

1. Insert elements using inorder traversal.
2. Increment the count for each node.
3. If the count is 1,  i.e. the node already exists, then instead of creating a new node, just increment the count.

### Solution code in C++ to remove duplicates in a Binary Search Tree(BST):

```#include<bits/stdc++.h>
using namespace std;

struct node
{
int data;
int count;
node* left;
node* right;
};

/*Function to create a new node*/
node* newNode(int key)
{
node* temp = new node;
temp->data = key;
temp->count = 1;
temp->left = NULL;
temp->right = NULL;
return temp;
}

/*Function for printing inorder traversal of nodes*/
void Inorder(node *root)
{
if(!root)
return;

Inorder(root->left);
cout << root->data;
if(root->count > 1)
cout<<"("<<root->count<<")";
cout<<" ";
Inorder(root->right);
}

/*Function to insert nodes in the tree while
increasing count in case of duplicate elements*/
node* createTree(node* root, int key)
{
if(!root)
return newNode(key);

if(key < root->data)
root->left = createTree(root->left, key);

else if(key > root->data)
root->right = createTree(root->right, key);

else

(root->count)++;

return root;
}

int main()
{
/*      10(2)
/     \
5      15
/  \    /  \
1   8   12   20(3)*/

node *root;
root = createTree(root,10);
createTree(root,5);
createTree(root,15);
createTree(root,10);
createTree(root,20);
createTree(root,20);
createTree(root,1);
createTree(root,8);
createTree(root,12);
createTree(root,20);

Inorder(root);

return 0;

}```

### Output:

```1 5 8 10(2) 12 15 20(3)
```