binary-search-tree# Insert duplicate values in a binary search tree

Can i **insert the same value** in a *binary search tree*?
And if I can, should this insert happen at the left or right of the existing node with that value?

Can I insert 23 to this tree?

Solution

Yes, unless otherwise specified by the actual context, a binary search tree can have duplicates. There is no rule for choosing a side.

Moreover, even if a side is agreed upon, binary search trees are typically self-balancing, and that means that this choice of side will not be maintained.

For instance, imagine the extreme case where only the value 42 is inserted in a tree, like five times, and we would agree that duplicates are inserted in the right subtree, then we would get this tree:

```
42
\
42
\
42
\
42
\
42
```

However, the BST would be rebalanced after a few inserts, and the resulting tree would be more like this (by that rebalancing):

```
42
/ \
42 42
\ \
42 42
```

And now it is clear you cannot assume at which side duplicate values could be stored.

Another approach is to allow duplicates but not store them as separate nodes. Instead you could make the "payload" (if any) an array of data that was inserted with the same key. Or, if there is no payload to go with a key, have a *counter* at each node indicating how often that key was inserted.

This might be preferable.

- Bad Operand Types for Binary Operator ">"?
- Convert a sorted array into a height-balanced binary search tree by picking middle element -- why does it work?
- Red Black Tree | is this tree balanced?
- Is the inorder predecessor of a node with no left subtree and being the left child of its parent always its grandparent?
- Is the Inorder Predecessor of a Node with a Left Subtree Always a Leaf Node in a Binary Search Tree?
- Correctness of Deletion algorithm of BST in CLRS
- Split a binary search Tree
- BST(Binary Search Tree) Testdome in Python
- Balanced Binary Tree Vs Balanced Binary Search Tree
- Does this algorithm for converting a Binary Search Tree into a sorted linked list on Wikipedia have a bug in it?
- Difference between binary tree and binary search tree
- Why is it impossible to convert a Min Heap to a Binary Search Tree (BST) in O(n) time?
- Binary Search Tree Insertion Method in Java
- Can we construct BST from inorder sequence?
- How can I get array output instead of memory location when printing TreeNode?
- What is the importance of implementing binary search trees (BST) for our database?
- Morris traversal leads to exception on LeetCode: address sanitizer , stack overflow
- Balancing a Binary Search Tree (BST)
- Is there a balanced BST with each node maintain the subtree size?
- Advantage of B+ trees over BSTs?
- Hashmap using Binary search tree incorrect implementation?
- Binary Search tree python. Iterative search
- How to print a binary search tree in level order, including the null values
- Segmentation fault while implementing a binary tree in c
- special property of the root of a BST - middle value?
- Why is my code deadlocking? Java fine-grained concurrent BST implementation attempt failed
- Insert duplicate values in a binary search tree
- What is a zip tree, and how does it work?
- can a binary search tree has two branches only?
- Find the missing value in a complete BST populated by each number from 1 to 2^K, where K is the number of levels