title: Building an AVL Tree out of Binary Search Tree
body: <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>