How to handle duplicates in Binary Search Tree ? | Java 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 )
class GFG { static class node { int key ; int count ; node left , right ; } ; static node newNode ( int item ) { node temp = new node ( ) ; temp . key = item ; temp . left = temp . right = null ; temp . count = 1 ; return temp ; } static void inorder ( node root ) { if ( root != null ) { inorder ( root . left ) ; System . out . print ( root . key + " ( " + root . count + " ) ▁ " ) ; inorder ( root . right ) ; } } static node insert ( 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 ; } static node minValueNode ( node node ) { node current = node ; while ( current . left != null ) current = current . left ; return current ; } static node deleteNode ( 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 ) { node temp = root . right ; root = null ; return temp ; } else if ( root . right == null ) { node temp = root . left ; root = null ; return temp ; } node temp = minValueNode ( root . right ) ; root . key = temp . key ; root . right = deleteNode ( root . right , temp . key ) ; } return root ; } public static void main ( String [ ] args ) { 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 ) ; System . out . print ( " Inorder ▁ traversal ▁ of ▁ " + " the ▁ given ▁ tree ▁ " + "NEW_LINE"); inorder ( root ) ; System . out . print ( " Delete 20 "); root = deleteNode ( root , 20 ) ; System . out . print ( " Inorder ▁ traversal ▁ of ▁ " + "the modified tree NEW_LINE"); inorder ( root ) ; System . out . print ( " Delete 12 "); root = deleteNode ( root , 12 ) ; System . out . print ( " Inorder ▁ traversal ▁ of ▁ " + "the modified tree NEW_LINE"); inorder ( root ) ; System . out . print ( " Delete 9 "); root = deleteNode ( root , 9 ) ; System . out . print ( " Inorder ▁ traversal ▁ of ▁ " + "the modified tree NEW_LINE"); inorder ( root ) ; } }