Data Structures u0026 Algorithms: Binary Search Trees and Balanced BSTs Quiz

This challenging quiz assesses knowledge of Binary Search Trees including insertion, deletion, search operations, as well as principles behind balanced BSTs like AVL and Red-Black Trees.

1. BST Insertion Properties

   When inserting a new key into a binary search tree containing the values 7, 3, 15, and 10, which property ensures the correct placement of the new key?

   1. Each inserted key must be greater than all keys in the tree
   2. Each left child key is less than its parent and each right child key is greater
   3. All root-to-leaf paths must be the same length
   4. The tree has a maximum of two levels per branch
   5. Nodes must have unique values only when they are leaves

2. Deletion with Two Children

   When deleting a node with two children in a binary search tree, which value is typically used to replace the deleted node's value?

   1. A random leaf node's value
   2. The post-order predecessor of the node
   3. The in-order successor of the node
   4. The level-order maximum of the left subtree
   5. The pre-order predecessor of the node

3. BST Search Performance

   Given a completely unbalanced (degenerated) BST formed by inserting the sequence 1, 2, 3, 4, 5, what is the time complexity of searching for the value 5?

   1. Θ(log n)
   2. O(1)
   3. O(n^2)
   4. O(n)
   5. O(log log n)

4. AVL Tree Rotations

   Suppose you insert keys 10, 20, and 30 (in that order) into an empty AVL tree; which rotation will be necessary to rebalance the tree?

   1. A double right-left rotation
   2. A single left rotation
   3. No rotation needed
   4. A double left-right rotation
   5. A single right rotation

5. AVL Balance Factor

   In an AVL tree, what is the range of the balance factor allowed at every node to ensure height balance?

   1. 0, 1, or 2
   2. -1 or +1 only
   3. Any integer
   4. -2, -1, or 0
   5. -1, 0, or +1

6. Red-Black Tree Properties

   Which is NOT a property of red-black trees among the following options?

   1. Every simple path from a node to its descendant leaves contains the same number of black nodes
   2. The root must always be black
   3. Red nodes may not have red children
   4. Every leaf (NIL) is black
   5. All left children must be black

7. Red-Black Tree Height Bound

   If a red-black tree has n internal nodes, which statement best describes the worst-case height?

   1. Less than √n
   2. Exactly log₂n
   3. No more than 2 × log₂(n + 1)
   4. Exactly equal to n
   5. At least log₃n

8. BST Deletion Case Recognition

   Given a node to delete in a BST where the node has only one child, what is the correct approach for removal?

   1. Recolor the child node black
   2. Swap the node with the leftmost node in the tree
   3. Replace the node with its sole child
   4. Leave the node but remove its child
   5. Increase the key by 1 and search again

9. AVL Tree Insertion Complexity

   What is the worst-case time complexity for inserting a key into an AVL tree of n nodes?

   1. Θ(√n)
   2. O(log n log n)
   3. O(n)
   4. O(1)
   5. O(log n)

10. Red-Black Tree Color Flip Scenario

    During an insertion into a red-black tree, when both the parent and parent’s sibling (uncle) are red, which operation must be performed first to maintain balance?

    1. Recolor the newly inserted node to black
    2. Single right rotation at the parent
    3. Double left-right rotation at the grandparent
    4. Recolor parent and uncle to black, grandparent to red
    5. Remove the parent node