# all possible binary search trees

Write down all binary search trees that can be produced by any permutation of the keys $\{1,2,3\}$.

I am new to this but is the answer simply this:

{root}(1), {left of root}(NIL), {right of root}(3), {left of 3}(2), {right of 3}(NIL)

and

{root}(2), {left of root}(1), {right of root}(3)

and

{root}(3), {left of root}(2), {right of root}(NIL), {left of 2}(1), {right of 2}(NIL)

I cant think of any more..

• are the trees I have so far correct? also, I cant think of any more. Mar 25 '15 at 13:20

There are six permutations of the given keys, so you need six trees, perhaps with some duplicates. You did not give a tree for 123, for example, which is

{root}(1), {left of root}(NIL), {right of root}(2), {left of 2}(NIL), {right of 2}(3)

The trees you gave look right.

By "produced by any permutation of the keys" the question probably means to take each permutation and add the numbers to an empty binary search tree in that order, using the standard easy way to add a new node without balancing.

The six permutations are:

123

132

213

231

312

321

The permutations you used for the three in your question are 132, 213, and 321, although your second one also works for 231.

There are other trees that could possibly be stored, but they would never result from the standard routine to add a note. For example, you give this example in your second comment:

{root}(2), {left of root}(1), {right of root}(NIL), {left of 1}(NIL), {right of 1}(3)

And that is indeed a binary search tree. However, there is no way to get the tree with the standard insertion routine. If you add 2 to an empty tree you get 2 at the root. If you then add 1 it gets added to the left of the root 2. However, if you then add 3 the routine sees that the 3 is greater than the root 2 so the 3 gets added to the right of the root 2, and the routine never even looks at the 1. So the resulting tree is the same as the second tree given in the original question.

Using the standard insertion routine, there are five trees that result from the six permutations of 123: the three given in the original question, the one I give in my answer, and the one you give in your first comment under this answer. The second tree in the original question is obtained twice, for 213 and for 231. All this is if the standard insert routine is used. If a non-standard routine is used, this answer is wrong... but such a non-standard routine would need to be stated at the start.

For clarity, here are the five possible binary search trees, with the permutation(s) that result in that tree. This list leaves out the trees that could possible be stored but could not result from using the standard insert/add routine on an empty tree. If this is an assignment, you would be wise to clarify if your list is supposed to include those impossible-to-get trees or not. Since the question you wrote says "that can be produced by any permutation of the keys" I believe those trees should be left out of your list: why else would the problem mention permutations? --I just realized that those trees meet some definitions of "binary search tree" but not all. You may want to check your particular definition.

123: {root}(1), {left of root}(NIL), {right of root}(2), {left of 2}(NIL), {right of 2}(3)

132: {root}(1), {left of root}(NIL), {right of root}(3), {left of 3}(2), {right of 3}(NIL)

213, 231: {root}(2), {left of root}(1), {right of root}(3)

312: {root}(3), {left of root}(1), {right of root}(NIL), {left of 1}(NIL), {right of 1}(2)

321: {root}(3), {left of root}(2), {right of root}(NIL), {left of 2}(1), {right of 2}(NIL)

• and there is {root}(3), {left of root}(1), {right of root}(NIL), {left of 1}(NIL), {right of 1}(2) but now I seriously cant think of anymore Mar 25 '15 at 13:30
• {root}(2), {left of root}(1), {right of root}(NIL), {left of 1}(NIL), {right of 1}(3), now that is six. So are there exactly six then since 3!=6? are there any more? Mar 25 '15 at 13:38
• OK we are definitely using the standard routine, but if we use this standard routine, for the six permutations, we get as you said, 6 trees but the 213 and 231 trees are the same so we actually get 5 different trees. So what exactly is this last tree? Mar 26 '15 at 13:18
• because I would think that any tree that isn't obtainable by the standard routine wouldn't be valid... I am not sure Mar 26 '15 at 13:34
• thanks for the edit. I highly doubt they would want us to show trees that are impossible to get. But that means there are not 3! possible trees then which is confusing me. there is in this case 3!-1. If there were n elements, how many possible trees can be produced? I thought at first it would be n! but clearly if n-=3, this is not the case. This is really frustrating... Mar 26 '15 at 14:24