In a Binary Search Tree (BST), all keys in left subtree of a key must be smaller and all keys in right subtree must be greater. So a Binary Search Tree by definition has distinct keys and duplicates in binary search tree are not allowed.

How to allow duplicates where every insertion inserts one more key with a value and every deletion deletes one occurrence?

A **Simple Solution** is to allow same keys with count. For example consider insertion of keys 3, 6, 7, 8, 8, 8, 10, 12, 12 in an empty Binary Search Tree [Read more…]