Skip to main content

AVL Tree Quiz Solutions

  1. What is the primary balance property that defines an AVL tree?

    • A) All nodes have at most 2 children
    • B) The height difference between left and right subtrees is at most 1
    • C) All leaf nodes are at the same level
    • D) The tree is a complete binary tree
      Answer: B) The height difference between left and right subtrees is at most 1
      Explanation: An AVL tree is a self-balancing binary search tree where the balance factor (the height difference between left and right subtrees) of any node is strictly restricted to -1, 0, or 1.

  2. How is the balance factor of a node formally calculated in an AVL tree layout?

    • A) Height of left subtree - Height of right subtree
    • B) Height of right subtree - Height of left subtree
    • C) Height of left subtree + Height of right subtree
    • D) Number of left children - Number of right children
      Answer: A) Height of left subtree - Height of right subtree
      Explanation: The standard balance factor formula is: Balance Factor = height(left_subtree) - height(right_subtree). Note that some textbooks use right minus left; however, it must always remain within 1.

  3. Which fundamental balance rotation is executed when a node's left child's left subtree causes a balance violation?

    • A) Left rotation
    • B) Right rotation
    • C) Left-Right rotation
    • D) Right-Left rotation
      Answer: B) Right rotation
      Explanation: A Left-Left (LL) imbalance case means the left-heavy side has become too deep. Applying a single right rotation fixes this imbalance immediately.

  4. What is the asymptotic time complexity for performing search operations in an AVL tree containing n nodes?

    • A) O(n)
    • B) O(log n)
    • C) O(n log n)
    • D) O(1)
      Answer: B) O(log n)
      Explanation: Because an AVL tree strictly limits structural skewing, its maximum height is strictly logarithmic relative to node count, ensuring an upper-bound execution track of O(log n) for lookups.

  5. What is the theoretical maximum height of an AVL tree configured with exactly 7 nodes?

    • A) 2
    • B) 3
    • C) 4
    • D) 5
      Answer: C) 4
      Explanation: Using the standard node-counting convention (where a single root has height 1), the minimum number of nodes required for a tree of height h satisfies the recurrence: N(h) = N(h-1) + N(h-2) + 1, with N(1) = 1 and N(2) = 2. Calculating the minimum nodes for each height: N(1)=1, N(2)=2, N(3)=4, and N(4)=7. Thus, the minimum number of nodes to achieve a height of 4 is exactly 7 nodes, making 4 the maximum height for a 7-node AVL tree.

  6. Which of the following numerical outcomes is NOT a valid balance factor for a stable AVL tree node?

    • A) 0
    • B) 1
    • C) -1
    • D) 2
      Answer: D) 2
      Explanation: Any balance factor absolute value greater than 1 (such as -2 or 2) represents an unstable layout state that triggers immediate rotation operations.

  7. During an insertion phase, under what precise layout structural conditions is a double Left-Right rotation required?

    • A) When the left child has a right-heavy subtree
    • B) When the right child has a left-heavy subtree
    • C) When the left child has a left-heavy subtree
    • D) When the root node becomes unbalanced
      Answer: A) When the left child has a right-heavy subtree
      Explanation: A Left-Right (LR) scenario occurs when a parent node is left-heavy, but its left child is right-heavy. An initial left rotation converts it into an LL case, followed by a right rotation to rebalance the tree.

  8. What is the worst-case time complexity for inserting a new data entry into an AVL tree with n nodes?

    • A) O(1)
    • B) O(log n)
    • C) O(n)
    • D) O(n log n)
      Answer: B) O(log n)
      Explanation: Locating the insertion point takes O(log n) steps. While walking back up the path to recompute balance variables and applying rotations takes constant structural times, the worst-case ceiling remains O(log n).

  9. At most, how many individual structural pointer rotations are needed to restore balance after a single insertion into an AVL tree?

    • A) 1
    • B) 2
    • C) O(log n)
    • D) O(n)
      Answer: B) 2
      Explanation: A single insertion can only trigger either a single rotation (1) or a double rotation (2) at the first unbalanced ancestor node. Once fixed, the balance of the entire path is restored.

  10. Which statement accurately captures the architectural relationship between AVL trees and Red-Black trees?

    • A) They are the same structure
    • B) Both are self-balancing BSTs
    • C) AVL trees are always faster
    • D) Red-Black trees require more rotations
      Answer: B) Both are self-balancing BSTs
      Explanation: Both are self-balancing binary search trees. AVL trees are more strictly balanced (requiring faster lookups but potentially more rebalancing rotations), whereas Red-Black trees tolerate a bit more skew to speed up structural edits.