Search code examples
treebinary-treebinary-search-tree

Is there a unique Binary Search Tree for given sequence of numbers?

So, this question was asked in my exam:

Make a BST for the following sequence of numbers: 45, 32, 90, 34, 68, 72, 15, 24, 30, 66, 11, 50, 10

I created the following BST: BST_ME

But it was marked wrong, and I was told that this is the correct one: BST_TECH

I was skeptical about the answer so I did the research and found this: Number of binary search trees over n distinct elements

This made me clear that more than 1 BST can exist for a set of numbers.

Then to make sure that the tree I created is BST, I took help from here: How do you validate a binary search tree?

and my BST is VALID!

Now before going to the professor again,

  • I want to know if the sequence in which numbers are given matters for the construction of BST or not? If yes, is the language of the question specifying me to add elements in order?
  • What is the approach to obtaining the BST given by the lecturer?

Note: The BST created by me isn't based on some special method, I created it using the basic properties of BST.

Solution

  • Yes, the order of insertion determines the resulting BST. As an extreme corner case, if you insert already ordered numbers you end up with a degenerate tree with only left or only right children, i.e. a list.

    I agree that the given language is ambiguous “a BST”, but most probably, by talking about a sequence, he implied that the numbers had to be inserted in the given order.

    Indeed, the BST as the right answer is exactly what you obtain by inserting the elements in the given order.