Inserting an equal value element

algorithm binary-search-tree
Programatt picture Programatt · Feb 21, 2012 · Viewed 18.5k times · Source

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?

Answer

Unknown1987 picture Unknown1987 · Feb 21, 2012

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.

Related questions

Finding height in Binary Search Tree

I was wondering if anybody could help me rework this method to find the height of a binary search tree. So far, my code looks like this. However, the answer I'm getting is larger than the actual height by 1. But …

Read More
Heap vs Binary Search Tree (BST)

What is the difference between a heap and BST? When to use a heap and when to use a BST? If you want to get the elements in a sorted fashion, is BST better over heap?

Read More
How do you validate a binary search tree?

I read on here of an exercise in interviews known as validating a binary search tree. How exactly does this work? What would one be looking for in validating a binary search tree? I have written a basic search tree, …

Read More