In an AVL tree, for what range of balance factor (pivotal value) should rebalancing rotations be performed to maintain the height balanced property of the tree?

Introduction / Context:
AVL trees are self balancing binary search trees used in data structures and algorithms to guarantee logarithmic time complexity for insert, delete, and search operations. The key idea is that after each update, the tree checks a numeric measure called the balance factor or pivotal value for each node. This question asks for the specific range of the balance factor that triggers rebalancing rotations in an AVL tree in order to maintain the height balanced property.

Given Data / Assumptions:

• The tree in question is an AVL tree, that is, a self balancing binary search tree.
• The balance factor of a node is defined as height of left subtree minus height of right subtree.
• An AVL tree must satisfy the property that for every node, the balance factor must remain between -1 and 1 inclusive.
• If the balance factor exceeds this range, rotations are applied to restore balance.

Concept / Approach:
The balance criterion for AVL trees is very specific. For each node, the balance factor can be -1, 0, or 1. When an insertion or deletion causes the balance factor of some node to become greater than 1 or less than -1, the AVL tree is considered unbalanced. At that point, one of the rotation cases (left left, right right, left right, or right left) is applied to restore the balance factor back into the allowed range. Therefore, the correct option must clearly state that rebalancing occurs when the balance factor is outside the interval [-1, 1].

Step-by-Step Solution:
Step 1: Recall the definition of balance factor = height(left subtree) - height(right subtree). Step 2: Remember the AVL property: for every node, balance factor must be -1, 0, or 1. Values in this range mean the node is balanced. Step 3: If an insertion makes the left subtree two levels higher than the right (balance factor greater than 1) or the right subtree two levels higher than the left (balance factor less than -1), the node becomes unbalanced. Step 4: At this point, we perform appropriate rotations to bring the balance factor back to a value in the range -1 to 1. Step 5: Therefore, we rebalance when balance factor is greater than 1 or less than -1, which matches option (a).

Verification / Alternative check:
As a quick verification, think of a perfectly balanced AVL tree where each node has balance factor 0. If you insert nodes skewed to one side, you may create a node with balance factor 2 or -2. These values are outside the acceptable range and trigger rotations. Conversely, a node with balance factor 1 or -1 is still considered balanced in AVL terminology and does not immediately require a rotation. This matches the rule described in option (a) and confirms the answer.

Why Other Options Are Wrong:
Option (b) describes the range where the tree is already balanced and no rotation is needed, so it cannot be the trigger condition. Option (c) and option (d) are incomplete because they consider only one side of the imbalance and ignore the symmetric case; AVL trees treat imbalance on either side (greater than 1 or less than -1) as a reason to rebalance. A correct answer must mention both positive and negative violations of the allowed range.

Common Pitfalls:
A common mistake is to assume that any nonzero balance factor implies imbalance. Students sometimes think that a balance factor of 1 or -1 is unacceptable, but in AVL trees these values are allowed. Another pitfall is to forget the absolute value view and only focus on one side, such as balance factor greater than 1, without considering the mirrored case balance factor less than -1. Remembering that AVL requires the absolute value of the balance factor to be less than or equal to 1 helps avoid confusion in exams.

Final Answer:
When the balance factor is greater than 1 or less than -1.