BST with duplicates

Question

I know that, BST does not allow duplicates. For example, if I have a word "RABSAB".

The Binary search tree for the above string is:

    R
    /\
   A  S
    \
     B

What if we wanted to include the duplicates in the tree. How the tree gonna change? I was asked this question in an interview.

They asked me to draw:

1. a binary tree
2. an unbalanced Binary Search Tree
3. a binary search tree without duplicates
4. a binary search tree with duplicates

Any Help is appreciated!

PS: Help me by drawing the related trees

Answer 1

Rule to insert in a binary Search tree without duplicate is:

1. Go left if element is less than root
2. Go right if the element is greater than root.

And to allow duplicate entries you have to modify the rule like bellow:

1. Go left if the element is less or equal root
2. Go right if the element is greater than root.

or

1. Go left if the element is less than root
2. Go right if the element is greater or equal root.

or

1. Go left if the element is less than root
2. Go right if the element is greater than root.
3. Increase the count if the element is equal to the root.

So your BST for word "RABSAB", with duplicates can be like:

     R
    / \
   A   S
  / \
 A   B
    /
   B

Or,

     R
    / \
   A   S
    \
     A
      \
       B
        \
         B

or

    R(1)
   /  \
  /    \
 A(2)  S(1)
  \
   \
   B(2)

In First two cases, both insertion and search becomes bit complex! You will find it here with great deal of explanation!

And the third case is somewhat easier to maintain.

All of them are used successfully to allow duplicates, now the choice is yours!