Which side do we place a node if it is equal to the parent in a binary search tree

Question

I am learning data structures and algorithms. In particular, I am learning Binary Search Trees (BSTs).

My question, as the title hints, is, if we are placing a value, and it is equal to its parent, which side do we place it? The left side is for values lesser than the parent, and the right side is for values greater than the parent. So, where do we place a value equal to the parent?

Thanks for any help on this.

Answer 1

There isn’t a universally agreed upon standard way to do this. Some people don’t allow BSTs to store duplicates at all, essentially defining this problem away. (That’s what you often see when using trees for maps and sets). Other implementations might store all equal keys in the same node, perhaps by using a linked list. Others might say that the left subtree holds smaller keys while the right subtree holds keys greater than or equal to the node’s own key.

Each of these approaches has advantages and disadvantages, and it’s up to you to select which one is best for your use case.