How to handle duplicates in Binary Search Tree ? | C ++ program to implement basic operations ( search , insert and delete ) on a BST that handles duplicates by storing count with every node ; A utility function to create a new BST node ; A utility function to do inorder traversal of BST ; A utility function to insert a new node with given key in BST ; If the tree is empty , return a new node ; If key already exists in BST , increment count and return ; Otherwise , recur down the tree ; return the ( unchanged ) node pointer ; Given a non - empty binary search tree , return the node with minimum key value found in that tree . Note that the entire tree does not need to be searched . ; loop down to find the leftmost leaf ; Given a binary search tree and a key , this function deletes a given key and returns root of modified tree ; base case ; If the key to be deleted is smaller than the root 's key, then it lies in left subtree ; If the key to be deleted is greater than the root 's key, then it lies in right subtree ; if key is same as root 's key ; If key is present more than once , simply decrement count and return ; ElSE , delete the node node with only one child or no child ; node with two children : Get the inorder successor ( smallest in the right subtree ) ; Copy the inorder successor 's  content to this node ; Delete the inorder successor ; Driver Code ; Let us create following BST 12 ( 3 ) / \ 10 ( 2 ) 20 ( 1 ) / \ 9 ( 1 ) 11 ( 1 )
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct node { int key ; int count ; struct node * left , * right ; } ; struct node * newNode ( int item ) { struct node * temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ; temp -> key = item ; temp -> left = temp -> right = NULL ; temp -> count = 1 ; return temp ; } void inorder ( struct node * root ) { if ( root != NULL ) { inorder ( root -> left ) ; cout << root -> key << " ( " << root -> count << " ) ▁ " ; inorder ( root -> right ) ; } } struct node * insert ( struct node * node , int key ) { if ( node == NULL ) return newNode ( key ) ; if ( key == node -> key ) { ( node -> count ) ++ ; return node ; } if ( key < node -> key ) node -> left = insert ( node -> left , key ) ; else node -> right = insert ( node -> right , key ) ; return node ; } struct node * minValueNode ( struct node * node ) { struct node * current = node ; while ( current -> left != NULL ) current = current -> left ; return current ; } struct node * deleteNode ( struct node * root , int key ) { if ( root == NULL ) return root ; if ( key < root -> key ) root -> left = deleteNode ( root -> left , key ) ; else if ( key > root -> key ) root -> right = deleteNode ( root -> right , key ) ; else { if ( root -> count > 1 ) { ( root -> count ) -- ; return root ; } if ( root -> left == NULL ) { struct node * temp = root -> right ; free ( root ) ; return temp ; } else if ( root -> right == NULL ) { struct node * temp = root -> left ; free ( root ) ; return temp ; } struct node * temp = minValueNode ( root -> right ) ; root -> key = temp -> key ; root -> right = deleteNode ( root -> right , temp -> key ) ; } return root ; } int main ( ) { struct node * root = NULL ; root = insert ( root , 12 ) ; root = insert ( root , 10 ) ; root = insert ( root , 20 ) ; root = insert ( root , 9 ) ; root = insert ( root , 11 ) ; root = insert ( root , 10 ) ; root = insert ( root , 12 ) ; root = insert ( root , 12 ) ; cout << " Inorder ▁ traversal ▁ of ▁ the ▁ given ▁ tree ▁ " << endl ; inorder ( root ) ; cout << " Delete 20 " root = deleteNode ( root , 20 ) ; cout << " Inorder ▁ traversal ▁ of ▁ the ▁ modified ▁ tree ▁ STRNEWLINE " ; inorder ( root ) ; cout << " Delete 12 " root = deleteNode ( root , 12 ) ; cout << " Inorder ▁ traversal ▁ of ▁ the ▁ modified ▁ tree ▁ STRNEWLINE " ; inorder ( root ) ; cout << " Delete 9 " root = deleteNode ( root , 9 ) ; cout << " Inorder ▁ traversal ▁ of ▁ the ▁ modified ▁ tree ▁ STRNEWLINE " ; inorder ( root ) ; return 0 ; }