3-element binary search trees

Question

I'm working through a past exam paper for my advanced programming course and I've gotten stuck at this question

What property must the values in a binary search tree satisfy? How many different binary search trees are there containing the three values 1 2 3? Explain your answer.

I can answer the first part easily enough but the second bit, about the number of possible trees has me stumped. My first instinct is to say that there is only a single tree possible, with 2 as the root because the definition says so, but this question is work 8 marks out of a total of 100 for the entire paper, so I can only assume that it's a trick question, and there's a more subtle explanation, but there's nothing in the lecture notes that explains this. Does anyone know who to answer this question?

Answer 1

If I remember correctly, the root of the tree does not have to be the "middle element". Thus there are a few more combinations of trees:

    2
1        3
or
1
    2
        3
or
1    
        3
    2
or
        3
    2
1
or
        3
1
    2

Maybe I forget a few, but I think you'll get the idea. Just for my notation: Newline meets get down in the tree, right and left of the upperline showes whether it is right or left of its parent node ;)

Answer 2

I think that a trick is that a tree can be a degenerate one (effectively, a linked list of elements):

1
 \
  2
   \
    3

And variations thereof.

Also, are these trees considered to be identical ?

  2        2
 / \      / \
3   1    1   3

Answer 3

Try to think about all possible binary trees with these three nodes. How many of those trees fulfill the property of binary search tree?

Answer 4

The question doesn't say that the tree is balanced, so think about whether 1 or 3 can be at the root node.