title: Worst Case number of rotations for BST to AVL algorithm?
body: <p>I have a basic algorithm below and I know that the worst case input BST is one that has degenerated to a linked list from inserts to only one side.</p>
  
  <p>How would I compute the worst case complexity in terms of number of rotations for this BST to AVL conversion algorithm?  </p>
  
  <pre><code>IF tree is right heavy
  {
    IF tree's right subtree is left heavy
    {
       Perform Double Left rotation 
    }
    ELSE
    {
       Perform Single Left rotation
    }
  }
  ELSE IF tree is left heavy
  {
    IF tree's left subtree is right heavy
    {
       Perform Double Right rotation
    }
    ELSE
    {
       Perform Single Right rotation
    }
  }
  </code></pre>