0

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.

Vansh
  • 3
  • 4

2 Answers2

0

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.

gigabytes
  • 3,104
  • 19
  • 35
  • Thanks for quick reply. Can you confirm that the BST_TECH is created by added elements in given order? – Vansh Dec 12 '17 at 11:52
  • Yes, it seems this is the case. It’s not hard to follow the numbers going through the tree as they are inserted. Try to implement the insertion procedure and you’ll see the result. – gigabytes Dec 12 '17 at 11:55
  • O...yes, i see it now. I will still try to obtain at least half the marks (3) for given question, i just need 2 more marks to upgrade the grade. Thank you again for answer. – Vansh Dec 12 '17 at 12:01
0

Traverse it From Left to Right Take left part (from starting) as a Root then from starting(traverse) see who is smaller or bigger If smaller then push it to the left part of root Else bigger then push it to the right part of root

enter image description here

Hope You Understand

Thanks & Regards
Deepak Yadav

M123
  • 1,203
  • 4
  • 14
  • 31
Deepak Yadav
  • 1