title: AVL Tree Balancing
body: <p>I am working on an assignment that asks me to implement an AVL tree. I'm pretty sure I have the rotation methods correct, but I'm having trouble figuring out when to use them.</p>
  
  <p>For example, the explanation in the book says that I should climb up the same path I went down to insert the node/element. However, I can't have any parent pointers.</p>
  
  <p>Latest code:</p>
  
  <pre><code>public BinaryNode&lt;T&gt; insert(BinaryNode&lt;T&gt; node) {
      if (this.getElement().compareTo(node.getElement()) &gt; 0) {
          if (this.getLeftChild() != null) {
              BinaryNode&lt;T&gt; b = this.getLeftChild().insert(node);
  
              if(!this.isBalanced()) {
                  this.balance();
              }
  
              return b;
          } else {
              this.setLeftChild(node);
          }
  
      } else if (this.getElement().compareTo(node.getElement()) &lt; 0) {
          if (this.getRightChild() != null) {
              return this.getRightChild().insert(node);
          } else {
              this.setRightChild(node);
          }
      }
  
      return this;
  }
  </code></pre>
  
  <p>What I want to do here is climb back up the tree, but it can only check the balancing AFTER it inserts the node. Hence, this being in the else clause.</p>
  
  <p>I also tried putting the balance code where R Samuel Klatchko suggested, but checked the balance on each insert. For example: If one inserts 7, 9, 5, 3, and 1 consecutively, I get a null pointer exception when trying to insert 1.</p>
  
  <p>EDIT: One reason for the above may have something to do with the way I was doing the height. It works fine with a single right rotation if I calculate the height every time with height() but that breaks the O(log(n)) time of an AVL Tree.       </p>
  
  <p>Any thoughts on how to accomplish this?</p>