Exam question about inserting to a empty binary search tree

Question

I'm having trouble interpreting a certain question about inserting elements to a binary search tree. I'm familiar with preorder, postorder, and inorder traversals, but I'm unfamiliar with the following question:

Suppose that we insert the elements 3, 5, 6, 1, 2, 4, 7 in that order into an initially empty binary search tree.

If I'm only given a set of numbers that are inserted in that order, how am I supposed to make it into a binary search tree? Would 3 be the root? And would I just balance the other numbers to the correct subtree by myself? Wouldn't there be a lot of interpretations in that case? Is there a certain convention that is followed?

Thanks.

Answer 1

When you add an item to the tree, the existing tree is not reordered. The new item is only added to a leaf node. This means that when you first add 3, 3 will be the root node of the result. When you add 5, it will be on the right of 3, etc. This results in the following tree:

   3
 /   \
1     5
 \   / \
  2 4   6
         \
          7

Answer 2

Without any further information on rules about how the tree is to be balanced, I would have to assume that it's referring to a "naive" unbalanced tree.

So this:

         3
  /-----/ \-----\
 1               5
  \--\       /--/ \--\
      2     4         6
                       \-\
                          7