0
$\begingroup$

How do I construct a perfect BST from an unbalanced BST with $n$ elements (assuming that $n=2^i-1$, $i$ is natural). ** At the worst case of $O(n)$**.

$\endgroup$
0
$\begingroup$

A simple way is as follows: do a symmetric visit of the BST (in time $O(n)$) and write down the elements in increasing order to an array $A$. Then reconstruct the BST from $A$.

If you're fine with a recursive algorithm, and the positions of $A$ are indexed form $0$ to $n-1$, then the root $r$ of the new BST will be exactly the element $A[\frac{n-1}{2}]$. The elements in $A[0], \dots, A[\frac{n-1}{2}-1]$ will be those of the subtree $L$ rooted in the left child of $r$, and the elements in $A[\frac{n-1}{2}+1], \dots, A[n-1]$ will be in the subtree $R$ rooted in the right child of $r$.

Notice that $|L| = 1 + \frac{n-1}{2}-1 = \frac{2^i - 2}{2} = 2^{i-1}-1$ and $|R| = 1 + (n - 1) - (\frac{n-1}{2} + 1 ) = (n - 1) - \frac{n-1}{2} = \frac{n-1}{2} = 2^{i-1}-1$, so you can apply this algorithm recursively.

The time required is $T(n) = T(2^i - 1) = 2 T(2^{i-1} - 1) + \Theta(1)$, with $T(1)=\Theta(1)$, which has solution $T(n)=\Theta(n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.