29

I am currently studying binary search trees, and I was wondering what do you do if you try to insert an element that is the same value as the root? Where does it go?

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
Programatt
  • 786
  • 4
  • 11
  • 23
  • 2
    It's up to the designer of the tree. You can return an error. You can add it as if it was the tiniest bit greater than the existing value. You can have a special "multiple entries" object that takes the place of the existing object. It depends on what the tree is intended to be used for. – David Schwartz Feb 21 '12 at 20:37
  • Related [question](http://stackoverflow.com/q/300935/503900) with nice answer. – bigstones Sep 09 '13 at 12:12

1 Answers1

33

The definition of BST is that it is a ordered set, thus duplicates are not allowed to be inserted. This is usually due to more complex structures being built atop the BST. Depending on the desired behavior, you may want to throw an exception, error or silently ignore when duplicates are inserted.

However, depending on your comparison function you can store duplicates on the left or right subtree, but remember to keep your traversals and insertion sides consistent.

Unknown1987
  • 1,671
  • 13
  • 30