New answers tagged

2

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


-1

To have height 5, then it's an almost degenerate tree; ie you simply check possible ways to have only one node in left or right Coming out of root, 1st level, 2nd,... I think there are 10 options, but you have to check them manually maybe some of them cannot happen for this set of numbers The point is the main property of Binary Search Trees (left child <...


Top 50 recent answers are included