# tree-search algorithm with n steps

I have no idea how to do this. There are $n!$ possible binary search trees. There is the simple tree that has root $n$ and just keep going left-down to $n-1$ then $n-2$ until $1$ which requires $n$ steps.

I am unsure why the question says 'at least' because I cant see a way to make a tree that gives more than n steps. There seems to only be one tree that gives n steps so the answer would be $1/n!$ but that just seems so simple. Please help.

TREE-SEARCH algorithm$(x,k)$: searches for $k$ within the sub-tree rooted at $x$. If $x$=NIL, it means that the sub-tree is empty and $k$ cannot be found there.

1. If $x$=NIL, then return NOT-FOUND;

2. if $key[x]=k$, then return $x$ (success);

3. if $k<key[x]$, then TREE-SEARCH$(left[x],k])$;

4. if $k>key[x]$, then TREE-SEARCH$(right[x],k])$;

• going from root(n-1) to n is 1 step. Then going from n to 1 would be n-1 steps. so in total there is 1+n-1=n steps right... or am I missing something. – snowman Mar 25 '15 at 15:19
• when you make a binary search tree, you can choose how it is placed out. like in this example here math.stackexchange.com/questions/1205939/… – snowman Mar 25 '15 at 15:29
• To make this Question answerable, I think you need to specify not only the TREE-SEARCH algorithm (and how the steps are counted), but the tree construction algorithm. Saying "you can choose how it is placed out" merely suggests the location of $1$ could be anywhere in the tree and does not give a clear connection with the order of arrival that you highlight with the first sentence of your Question. – hardmath Mar 25 '15 at 16:13
• sorry, I was wrong. the second tree I talked about in the question isn't obtainable by the standard routine which is what you were thinking and convincing me about earlier. I have edited the question. It seems to me that there is only one tree that would give n steps, giving the answer 1/n! but that seems too simple... – snowman Mar 26 '15 at 13:42
• It occurs to me that I'm very likely telling you things you were supposed to learn next week, and this exercise was supposed to help motivate the algorithms you'll discuss later. – David K Mar 26 '15 at 17:47

HINT: The only way that a tree will find 1 in at least n steps is if the keys arrive in order $n,n-1,...,2,1$.
• @snowman I think your doubts about the $n!$ number of trees are good thinking. There are fewer than $n!$ possible trees in general. For example, if I guessed correctly what algorithm constructs your tree, the input 3,4,5,1,2 produces the same tree as 3,1,2,4,5 or 3,1,4,2,5. – David K Mar 26 '15 at 17:39