Is it possible to have multiple valid BSTs for a given set of data?

Question

Given a set of data in a binary search tree, like the numbers 1 to 10, is it possible for multiple balanced binary search trees to exist?

Or is there just one, unique balanced BST for that set of data?

Thanks

Answer 1

It all depends on the specific binary tree data structure being used, the insertion algorithm, the balancing criteria and the order of insertion, but yes - it's possible to have multiple equivalent and valid balanced BSTs for a given sequence of values.

For example, this is a valid Red/Black Tree where the numbers 1-10 were inserted in ascending order:

On the other hand, this is a valid AVL Tree, where the numbers 1-10 were inserted exactly in the same order as in the Red/Black Tree:

Clearly, the trees are not exactly the same - but the ordering and balancing properties hold for both.