# For AVL Trees why is keeping a trit (left heavy, right heavy or balanced) sufficient?

I was listening to Eric Demaine's video lecture on AVL trees and there was a claim that comes up that keeping a trit on each node (to indicate whether the node is left heavy, right heavy or balanced) should be sufficient for all AVL tree operations, so essentially we don't need to keep heights of the node for every node. Can anyone prove to me why that would be the case?

• Most of us should be able to, and about every DS text introducing AVL-trees should give it (consult yours(?)). If I don't get it wrong, it is not a property of the node such attributed, any or both of its sub-trees or the tree rooted at the node in question: it is about the way balancing should be done. Jul 9 '15 at 18:44

In an AVL tree we aim to make the binary tree height balanced. Say the left subtree of a node has a height of $m$ and the right subtree has a height of $n$. The node therefore has a balance of $b=m-n$. We rotate the tree to restore it's balance if the balance of any node, $|b|>1$.
So the value of $b$ is either $-1,0, or 1$. Hence storing the balance of each node in a trit becomes much easier than say storing the height of each node, because all we need to do is check the balance.
That way, knowing the old balance (which is in $\{-1,0,1\}$) and if (and how) subtree heights changed is enough to know the new balance (which is in $\{-2,1,0,1,2\}$). If the balance is $-2$ or $2$ we rotate, of course, and restore balance (in that node).