In an AVL tree, what is a node's balance factor and which values are legal?
answer
- one small number stored per node
- it compares the two subtrees
- heights, not node counts
- left minus right
- one unit of slack in either direction
basics
~20 sA node's balance factor is its left subtree's height minus its right subtree's height. An AVL tree is valid when every node's factor is -1, 0 or +1 — a bound on heights, not on node counts.
solid answer
~50 sThe balance factor of a node is `height(left subtree) - height(right subtree)`, where an empty subtree gets a sentinel height (commonly -1, so a leaf has height 0). The AVL invariant is that **every** node in the tree has a balance factor in {-1, 0, +1}. Two things matter about that definition. First, it constrains **heights**, not sizes: a node whose left subtree holds 60 keys in height 5 and whose right subtree holds 6 keys in height 4 is perfectly legal AVL — an AVL tree is not required to be perfectly balanced or complete. Second, it is a *local* condition checked at each node, and enforcing it everywhere is exactly what pins the whole tree's worst-case height to about 1.44·log2(n). Implementations usually store the height (or the factor itself) in each node so the check is a subtraction rather than a subtree walk.
go deeper
Be ready to state the formula and the three legal values in one breath, and to compute the factor for a small hand-drawn tree bottom-up. Say the word 'height' explicitly — that one word is what the interviewer is listening for.
Explain why a per-node height difference of at most one is enough to bound the whole tree's height logarithmically, and why the field is stored rather than recomputed on each check.
Show that you know the invariant is violated transiently during insert and delete, and describe how the retrace path detects and repairs it without touching the rest of the tree.
Frame 'balanced' as a contract about worst-case path length, not about symmetry. When a team debates ordered structures, insist each candidate be described by the bound it guarantees and the per-node overhead it charges for that bound.
## What the number is An AVL tree is a binary search tree that keeps a small bookkeeping value at every node so it can notice, in constant time, when its shape has drifted. That value is the **balance factor**: ``` balance(n) = height(left(n)) - height(right(n)) ``` **Height** here means the length of the longest downward path from that node to a leaf, measured in edges. A leaf has height 0, and an empty subtree is given the sentinel height -1 so that a node with one leaf child and no other child computes `0 - (-1) = 1`. The other common convention counts nodes instead of edges (empty = 0, leaf = 1); either works, but the whole implementation must use one consistently, and mixing them is a classic source of off-by-one bugs in a rebalance routine. ## The invariant The AVL condition is: **for every node in the tree, `balance(n)` is -1, 0 or +1.** Not just the root, not just internal nodes — every one. A factor of 0 means the two sides are equally tall; -1 means the right side is one level taller; +1 means the left side is. Anything of magnitude 2 or more is a violation that the insert or delete routine must repair before the operation returns. ## Heights, not sizes — the misconception that costs the point The most common wrong answer is that an AVL tree keeps the two subtrees of each node at equal, or nearly equal, **node counts**. It does not, and it could not: a tree with 7 nodes can be split 1/5 across a root and still satisfy the invariant, because height grows logarithmically while size grows linearly. Consider a root whose left subtree is a full tree of height 3 (15 nodes) and whose right subtree is a single path of height 2 (3 nodes): balance factor `3 - 2 = 1`, legal AVL, five times as many nodes on one side as the other. "Balanced" in this family of structures is always a statement about the *worst-case path length*, never about symmetry of population. The related wrong answer is that AVL means *perfectly* balanced — all leaves at the same depth. That shape exists only when n is exactly 2^k - 1, so a structure that demanded it could not accept an arbitrary key at all without a full rebuild. The +/-1 slack is precisely what makes the invariant repairable with a constant amount of local surgery. ## Why one unit of slack is enough The payoff of a purely local rule is a global bound. Ask: what is the *fewest* nodes an AVL tree of height h can contain? Call it N(h). Its root must have one subtree of height h-1, and the invariant lets the other be as short as h-2, so `N(h) = 1 + N(h-1) + N(h-2)`, with `N(0) = 1` and `N(1) = 2`. That is a Fibonacci-shaped recurrence, so the minimum node count grows exponentially in h, which inverts to a height that grows logarithmically in n — worst case roughly `1.44·log2(n)`. In other words, the sparsest tree the invariant permits is still only about 44% taller than a perfect tree. A search, insert or delete therefore visits O(log n) nodes no matter what order the keys arrived in. ## Transient violation is normal During an insertion or deletion the tree is briefly out of contract: adding a node can push some ancestor to a factor of +/-2. That is expected. The operation retraces the path from the modified node toward the root, updating stored heights, and applies a rotation where it finds magnitude 2. "Every node is in {-1, 0, +1}" is an invariant *between* operations, not during them. A candidate who says a factor of 2 can never exist anywhere has memorised the rule without understanding the algorithm that maintains it. ## What it costs The bookkeeping is not free: each node carries an extra field (a small height integer, or two bits if you store only the factor), and every insert and delete must update it along the retrace path. That is the price of the tighter height bound, and it is why the choice among self-balancing schemes is a workload question rather than a correctness one. ## Reading a tree quickly To check a tree by hand, work bottom-up: leaves have height 0 and factor 0; each internal node's height is one more than the taller child's, and its factor is the difference. Doing it top-down forces you to recompute subtree heights repeatedly, which is both slower and where hand-traced answers usually go wrong.
- If every node in a tree has balance factor 0, what does that tell you?The tree is perfectly balanced — every leaf sits at the same depth — which is only possible when the node count is exactly 2^k - 1. It is a legal AVL tree, but AVL never requires it; demanding it would make most insertions impossible to satisfy without a full rebuild.
- Can a node's balance factor ever be +2 while the structure is still doing its job?Yes, transiently. An insertion or deletion can push an ancestor to magnitude 2, and the retrace step detects it and rotates before the operation returns. The invariant is a contract between operations, not a claim that magnitude 2 never appears in memory.
- How is the balance factor kept up to date cheaply?Each node stores its height (or the factor directly), so computing the factor is one subtraction rather than a subtree walk. After a structural change, only the nodes on the path from the change to the root can have stale heights, so an O(log n) retrace refreshes them.
It is like a rule that two stacks of shelving must not differ by more than one shelf in height — it says nothing about how many books sit on each shelf.
saying these in an interview costs you the question
- Says the two subtrees must hold the same number of nodes
- Claims AVL requires perfect balance with all leaves at one depth
- Defines the balance factor as a difference of subtree sizes
- Cannot say what height an empty subtree contributes
- Thinks the invariant applies only at the root