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.
If $x$=NIL, then return NOT-FOUND;
if $key[x]=k$, then return $x$ (success);
if $k<key[x]$, then TREE-SEARCH$(left[x],k])$;
if $k>key[x]$, then TREE-SEARCH$(right[x],k])$;