Consider there's a BST which has duplicate elements. You have to remove all the duplicate elements from the tree. The insertion in the BST when an equal key is found is random i.e, while inserting a key in the tree, if the said key is already present, the key can be inserted in either the left sub-tree or the right sub-tree, but still following the basic property of the BST. So all the keys on the left sub-tree of any node is less than or equal to the node and the keys on the right sub-tree of any node is greater than or equal to the node. How would you delete all the duplicate elements.
Please note, that if a key say for example 15 appears thrice in the entire tree, we don't remove all three instances, but delete just two, it doesn't matter which two.
There is the brute force approach of traversing the tree in PreOrder fashion. Then find and delete elements, on the left and the right subtree, which have their key equal to the said node.
Is there a better way to solve this problem?
