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:

a binary tree
an unbalanced Binary Search Tree
a binary search tree without duplicates
a binary search tree with duplicates

Any Help is appreciated!

PS: Help me by drawing the related trees

`BST` doesn't constraint that duplicates are not allowed, you can keep duplicate, read : [Strategy for duplicate entries in a binary search tree](http://stackoverflow.com/questions/7707321/strategy-for-duplicate-entries-in-a-binary-search-tree) — Grijesh Chauhan, May 24 '13 at 04:56
I was speaking in general. I read in wiki, in general BST wont allow duplicates. Can you help in drawing the BST for the given String? — user, May 24 '13 at 05:01
possible duplicate of [Are duplicate keys allowed in the definition of binary search trees?](http://stackoverflow.com/questions/300935/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 — Ciro Santilli OurBigBook.com, Apr 11 '15 at 09:39

score 20 · Accepted Answer · edited May 23 '17 at 10:31

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

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

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

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

or

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

or

Go left if the element is less than root
Go right if the element is greater than root.
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,

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!

You have provided me all the scenarios. – user May 24 '13 at 21:23 — user, May 24 '13 at 21:23
you are always going left in the duplicate cases? – Songo Dec 21 '13 at 18:27 — Songo, Dec 21 '13 at 18:27

Zim-Zam O'Pootertoot · Answer 2 · 2013-05-24T05:09:07.927

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;
}

edited May 24 '13 at 05:09

answered May 24 '13 at 05:01

Zim-Zam O'Pootertoot

17,888
4
41
69

keeping 'List data' would add the overhead off traversing the list then adding in to the list , keeping the counter suits better . – Hussain Akhtar Wahid 'Ghouri' Feb 14 '17 at 21:11

score 0 · Answer 3 · answered May 24 '13 at 05:04

In a normal BST insertion and search both occur based on less than(>) and greater than (<) rule.

You could instead try insertion on less than equal to (>=) or greater than equal to (<=) and try using the same rule for searching.

Alternatively you could include an array in every node to accommodate duplicate elements.

score 0 · Answer 4 · answered May 24 '13 at 05:09

For your input RABPAB, You can create a BST by using a LIST to store all the equal valued keys. All the equal valued keys are placed in the same level using a data structure capable of storing it.

The BST will look something like this,

     R
    / \
A--A   P
    \
  B--B

The Java code for your BST storing integer values could be like this,

class Node 
{
    Node left, right;
    int data[maxvalue];
}

Here maxvalue is the maximum possible equal valued keys.

BST with duplicates

4 Answers4

Linked