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

Solution 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!

Solution 2

One option is to modify the tree so that one branch will include the duplicates, for example have the left branches hold nodes that are less than or equal to the parent, alternatively have the right branches hold nodes that are greater than or equal to the parent

Another option is to store all duplicates in a node, so instead of

class Node {
    Node left, right;
    Object data;
}

you would instead have

class Node {
    Node left, right;
    List data;
}

or

class Node {
    Node left, right;
    Object data;
    int count;
}

Comments

[Ciro Santilli OurBigBook.com]

possible duplicate of Are duplicate keys allowed in the definition of binary search trees?, because any good answer to that question must consider how to implement such BSTs

[user]

You have provided me all the scenarios.

[Songo]

you are always going left in the duplicate cases?

[Hussain Akhtar Wahid 'Ghouri']

keeping 'List data' would add the overhead off traversing the list then adding in to the list , keeping the counter suits better .