title: Perfect Balanced Binary Search Tree
body: <p>I have an theoretical question about <code>Balanced BST</code>.</p>
  
  <p>I would like to build <code>Perfect Balanced Tree</code> that has <code>2^k - 1</code> nodes, from a regular <code>unbalanced BST</code>. The easiest solution I can think of is to use a sorted <code>Array/Linked list</code> and recursively divide the array to sub-arrays, and build <code>Perfect Balanced BST</code> from it.</p>
  
  <p>However, in a case of extremely large Tree sizes, I will need to create an <code>Array/List</code> in the same size so this method will consume a large amount of memory.</p>
  
  <p>Another option is to use <code>AVL</code> rotation functions, inserting element by element and balancing the tree with rotations depending on the Tree Balance Factor - three height of the left and right sub trees.</p>
  
  <p>My questions are, am I right about my assumptions? Is there any other way to create a perfect <code>BST</code> from unbalanced <code>BST</code>?</p>