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)

Remove duplicates from a Binary Search Tree solution(BST):

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) 

Time Complexity:O(nlogn)