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!

"official definition"? What would you consider "official"? What level of authority is required here? — S.Lott
– S.Lott, Commented Jan 2, 2012 at 18:35
I guess it's not so much level of authority, as much as it is what is the most commonly accepted definition of BSTs regarding duplicate entries. — Tareq
– Tareq, Commented Jan 2, 2012 at 19:14

TonySalimi · Accepted Answer · 2012-01-02 18:57:11Z

6

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:

enter image description here

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:

enter image description here

edited Jan 2, 2012 at 18:57

answered Jan 2, 2012 at 18:32

TonySalimi

8,5054 gold badges39 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Saeed Amiri Over a year ago

Wow very interesting and meek answer.

light_303 · Accepted Answer · 2012-01-02 18:25:05Z

3

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

answered Jan 2, 2012 at 18:25

light_303

2,1313 gold badges20 silver badges37 bronze badges

3 Comments

Niklas B. Over a year ago

The external link is not very helpful in this context.

Nikolay Polivanov Over a year ago

In trees where left child is < than the node and right child is >= than the node, it's not a big deal. When first node is found one just can check right childs to obtain all duplicates.

C. Reed Over a year ago

Of course each node could just contain a count of the number of times the element appears

Collectives™ on Stack Overflow

Duplicate Entries in Binary Search Tree

2 Answers 2

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related