What's the case for duplications in BST?

Question

How to solve the problem with duplication in Binary Search Tree?

Answer 1

It's up to your comparison check: if equal and smaller are equivalent, duplicates will be placed in the "smaller" node, otherwise they're in the "larger" node. Besides this, there shouldn't be an issue with duplicates, unless you want to avoid them of course, in which case you need an extra equality check.

Answer 2

I am not really sure what you are asking. But that won't stop me from posting an answer.

Usually, duplicate keys are disallowed in a BST. That tends to make things a lot easier, and it is a condition that is easy to avoid.

If you do want to allow duplicates, then insertions are not a problem. You can just stick it either in the left subtree or the right subtree.

The problem is that you can't count on the duplicates being on a particular side if it is a self-balancing tree like an AVL-tree or a red-black-tree. It seems like this might be a problem for deletions, but I once implemented an AVL-tree that made no special provisions for duplicates, and it had no problems at all.

Deleting a node from an AVL tree involves (1) finding the node, (2) replacing that node with either the greatest key in the left subtree or the smallest key in the right subtree, and then recursively deleting that node. If there is no subtree, then nothing more needs to be done.

In practice, deleting a node with duplicates means that the node with the sought key nearest the root will be replaced with something, either a node with another key, or a node with the same key. Either way, the ordering constraints are not violated, and everything proceeds with no trouble.

I don't know about red-black trees or other sorts of BSTs.