title: balancing an AVL tree (C++)
body: <p>I'm having the hardest time trying to figure out how to balance an AVL tree for my class. I've got it inserting with this:</p>
  
  <pre><code>Node* Tree::insert(int d)
  {
      cout &lt;&lt; "base insert\t" &lt;&lt; d &lt;&lt; endl;
      if (head == NULL)
          return (head = new Node(d));
      else
          return insert(head, d);
  }
  
  Node* Tree::insert(Node*&amp; current, int d)
  {
      cout &lt;&lt; "insert\t" &lt;&lt; d &lt;&lt; endl;
      if (current == NULL)
          current = new Node(d);
      else if (d &lt; current-&gt;data) {
          insert(current-&gt;lchild, d);
          if (height(current-&gt;lchild) - height(current-&gt;rchild)) {
              if (d &lt; current-&gt;lchild-&gt;getData())
                  rotateLeftOnce(current);
              else
                  rotateLeftTwice(current);
          }
      }
      else if (d &gt; current-&gt;getData()) {
          insert(current-&gt;rchild, d);
          if (height(current-&gt;rchild) - height(current-&gt;lchild)) {
              if (d &gt; current-&gt;rchild-&gt;getData())
                  rotateRightOnce(current);
              else
                  rotateRightTwice(current);
          }
      }
  
      return current;
  }
  </code></pre>
  
  <p>My plan was to have the calls to balance() check to see if the tree needs balancing and then balance as needed. The trouble is, I can't even figure out how to traverse the tree to find the correct unbalanced node. I know how to traverse the tree recursively, but I can't seem to translate that algorithm into finding the lowest unbalanced node. I'm also having trouble writing an iterative algorithm. Any help would be appreciated. :)</p>