# 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. 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/… 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. 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... 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. Mar 26 '15 at 17:47

## 1 Answer

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$.

• And the number of ways that these keys can arrive is n! Right? So the answer is 1/n!? Mar 26 '15 at 16:41
• yes that is correct Mar 26 '15 at 16:45
• How would you explain that if it isnt in that order, then there wouldn't be n steps to reach 1? Mar 26 '15 at 16:48
• @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. Mar 26 '15 at 17:39
• I know, this question is sooo badly written Mar 26 '15 at 17:40