Duplicate Entries in Binary Search Tree

Question

I have a very simple question regarding BSTs. I have seen multiple definitions of BSTs regarding duplicate entries. Some define BSTs as not allowing duplicate entries, others that node's left child is <= to the nodes value and the right child is greater than the node's value, and some definitions are the opposite of that ( left child is < than the node, right child is >=).

So my question is what is the official definition (if one exists) for BSTs regarding duplicate entries? For example what would a BST look like after inserting the values : 3, 5, 10, 8, 5, 10?

Thank you in advance for clarifying the definition and answering my question!

Answer 1

One of the well-known books in the algorithm and data structure area is the CLRS book, also known as the bible of data structures and algorithms:

According to the definition of this book, the duplicate entries are placed in the right tree of the node that contains the same key. As an example, take a look at the insertion algorithm of BSTs adopted from this book:

Answer 2

the important point is that not having duplicates in the tree assures the fast lookup times. If you have duplicates in one side of the node your search time will suffer because you have to go through all duplicates before you can continue.

http://en.wikipedia.org/wiki/Binary_search_tree