# Tag Info

$\Omega(n \log n)$ operations are needed. More precisely, starting from any given tree $T$ you can only reach $\exp(O(n+m))$ other trees in $m$ operations. The idea is to augment your information-theoretic argument with the observation that most operations commute. Note that we cannot hope to replace $O(n+m)$ with $O(m)$, since for $m = 1$ there can be $O(n) ... 2 The language of the question is a not quite clear to me. The question is open to two possible interpretations. Interpretation 1: Problem: For a given$n$we need to find the number of permutations of$\langle 1,2,3,..,n\rangle$such that if we build a binary search tree using that permutation as an input sequence we shall get a binary search tree of height ... 2 Let$T(n)$denote the number of ways in which$n$distinct numbers can form a binary tree of height$n-2$. Let$P(n)$denote the number of ways in which$n$distinct numbers can form a binary tree of height$n-1$. Then,$T(n) = 2 \cdot T(n-1) + 2 \cdot P(n-2)$The first two$T(n-1)\$ terms are due to choosing the smallest and the largest elements as roots. ...