dealing with duplicates in a bst

Question

My bst has to be able to cope with duplicate entries. Does anyone have any strategies for how to go about this that doesn't require excessive amounts of code? I thought of consistently adding duplicates to the right but then that will mess up the bst order. for example what happens when the duplicate has two children who in turn have two children?. inserting the duplicate is easy enough, but what is to be done with the node it replaced?

Answer 1

You could make the nodes of the binary search tree into linked lists.

class Data implements Comparable<Data>
{
   // These are the data elements in your binary search tree
}

class TreeNode
{
  TreeNode left; // elements less than current node, or null
  TreeNode right; // elements greater than current node, or null
  List<Data> items = new LinkedList<Data>();    
}

Here, treeNode.items is always a non-empty list, such that item1.compareTo(item2) == 0 for every item1 and item2 in treeNode.items.

To insert a duplicate element, you would find the relevant TreeNode object and add a new item to items.

The logic of finding elements is almost the same as you had before, except that once you find the relevant TreeNode object you have to walk the linked list.

Answer 2

As long as it's not a self balancing BST, I don't see a problem with putting equal nodes either at the left or right of the node that is equal to them.

Edit (after simonn's remark):

If the "duplicate node" in question already has 2 children, then simply insert the "new duplicate node" to the left and let the left child of the "old duplicate node" become the left child of the "new duplicate node".

Let me clarify with an example. The tree before inserting a duplicate:

    4'
   / \
  2   5
 / \
1   3

And now the element 4'' is inserted:

      4'
     / \
    4'' 5
   /
  2   
 / \
1   3

As long as the tree is not self balancing, you should be okay.