Building an AVL Tree out of Binary Search Tree
<p>I need to suggest an algorithm that takes BST (Binary Search Tree), <code>T1</code> that has <code>2^(n + 1) - 1</code> keys, and build an AVL tree with same keys. The algorithm should be effective in terms of worst and average time complexity (as function of <code>n</code>).</p>

<p>I'm not sure how should I approach this. It is clear that the minimal size of a BST that has <code>2^(n + 1) - 1</code> keys is <code>n</code> (and that will be the case if it is full / balanced), but how does it help me?</p>

<p>There is the straight forward method that is to iterate over the tree , each time adding the root of <code>T1</code> to the AVL tree and then removing it from <code>T1</code>: </p>

<ul>
<li>Since <code>T1</code> may not be balanced the delete may cost O(n) in worst case</li>
<li>Insert to the AVL will cost O(log n)</li>
<li>There are <code>2^(n + 1) - 1</code></li>
</ul>

<p>So in total that will cost <code>O(n*logn*2^n)</code> and that is ridiculously expensive.</p>

<p>But why should I remove from <code>T1</code>? I'm paying a lot there and for no good reason.
So I figured why not using tree traversal over <code>T1</code> , and for each node I'm visiting , add it to the AVL tree:</p>

<ul>
<li>There are <code>2^(n + 1) - 1</code> nodes so traversal will cost <code>O(2^n)</code> (visiting each node once)</li>
<li>Adding the current node each time to the AVL will cost <code>O(logn)</code></li>
</ul>

<p>So in total that will cost <code>O(logn * 2^n)</code>.
and that is the best time complexity I could think of, the question is, can it be done in a faster way? like in <code>O(2^n)</code> ?
Some way that will make the insert to the AVL tree cost only O(1)?</p>

<p>I hope I was clear and that my question belongs here.</p>

<p>Thank you very much,</p>

<p>Noam</p>