# How to construct a perfect BST from an unbalanced BST with n elements (assuming that n=(2^i)-1, i is natural)

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

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