title: The best way to calculate the height in a binary search tree? (balancing an AVL-tree)
body: <p>I'm looking for the best way to calculate a nodes balance in an <a href="http://en.wikipedia.org/wiki/AVL_tree" rel="noreferrer">AVL-tree</a>. I thought I had it working, but after some heavy inserting/updating I can see that it's not working correct (at all). </p>
  
  <p>This is kind of a two-part question, the first part would be how to calculate the height of a sub-tree, I know the definition <em>"The height of a node is the length of the longest downward path to a leaf from that node."</em> and I understand it, but I fail at implementing it. And to confuse me further this quote can be found on wikipedia on tree-heights <em>"Conventionally, the value -1 corresponds to a subtree with no nodes, whereas zero corresponds to a subtree with one node."</em></p>
  
  <p>And the second part is getting the balance factor of a sub-tree in an AVL tree, I've got no problem understanding the concept, <em>"get the height of your <code>L</code> and <code>R</code> sub-trees and subtract <code>R</code> from <code>L</code>"</em>. And this is defined as something like this: <code>BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]</code></p>
  
  <p>Reading on wikipedia says this on the first few lines describing insertions into an AVL tree: <em>"If the balance factor becomes -1, 0, or 1 then the tree is still in AVL form, and no rotations are necessary."</em></p>
  
  <p>It then goes on, saying this <em>"If the balance factor becomes 2 or -2 then the tree rooted at this node is unbalanced, and a tree rotation is needed. At most a single or double rotation will be needed to balance the tree."</em> - which I have no trouble grasping. </p>
  
  <p>But (yes, there's always a but).</p>
  
  <p>Here's where it gets confusing, the text states <em>"If the balance factor of R is 1, it means the insertion occurred on the (external) right side of that node and a left rotation is needed"</em>. But from m understanding the text said (as I quoted) that if the balance factor was within <code>[-1, 1]</code> then there was no need for balancing? </p>
  
  <p>I feel I'm so close to grasping the concept, I've gotten the tree rotations down, implemented a normal binary search tree, and on the brink of grasping AVL-trees but just seem to be missing that essential epiphany.</p>
  
  <p><strong>Edit:</strong> Code examples are preferred over academic formulas as I've always had an easier time grasping something in code, but any help is greatly appreciated.</p>
  
  <p><strong>Edit:</strong> I wish I could mark all answers as "accepted", but for me NIck's answer was the first that made me go "aha".</p>