Consider a *dynamic* hashing approach for 4-bit integer keys: 1. There is a main hash table of size 4. 2. The 2 least significant bits of a key is used to index into the main hash table. 3. Initially, the main hash table entries are empty. 4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand. 5. First, the $3^{\text{rd}}$ least significant bit is used to divide the keys into left and right subtrees. 6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the $4^{\text{th}}$ least significant bit. 7. A split is done only if it is needed, i.e., only when there is a collision. Consider the following state of the hash table. Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?

Let each 4-bit key be represented as $b_4 b_3 b_2 b_1$, where $b_1$ is the least significant bit (LSB) and $b_4$ is the most significant bit ($4^{\text{th}}$ LSB).

From the given hash table structure:

1. Index 00: Empty (no keys hashed to bucket 00).

2. Index 11: Exactly $1$ key hashed to 11 (no split occurred).

3. Index 10: Exactly $2$ keys hashed to 10, one having $b_3 = 0$ and the other having $b_3 = 1$ (causing a single split at level 1).

4. Index 01: Exactly $3$ keys hashed to 01:

   • One key with $b_3 = 0$ (left branch, no further split).

   • Two keys with $b_3 = 1$, which collide on $b_3$ and split on $b_4$ into $b_4 = 0$ and $b_4 = 1$.

Let's evaluate the options by converting each key to 4-bit binary:

• Option (A): Keys $\{5, 9, 4, 13, 10, 7\}$

  • $4 = 0100_2$ hashes to bucket 00. However, bucket 00 is empty. Thus, (A) is incorrect.

• Option (B): Keys $\{9, 5, 10, 6, 7, 1\}$

  • Keys hashing to 01 are $9 = 1001_2$ ($b_3=0$), $5 = 0101_2$ ($b_3=1$), and $1 = 0001_2$ ($b_3=0$).

  • Here, two keys have $b_3=0$ ($9$ and $1$), which would cause the left subtree ($b_3=0$) to split on $b_4$. But in the given diagram, the right subtree ($b_3=1$) is split. Thus, (B) is incorrect.

• Option (C): Keys $\{10, 9, 6, 7, 5, 13\}$

  • $10 = 1010_2 \implies$ bucket 10, $b_3=0$

  • $6 = 0110_2 \implies$ bucket 10, $b_3=1$ (two keys in 10, one with $b_3=0$ and one with $b_3=1$)

  • $7 = 0111_2 \implies$ bucket 11, single key

  • $9 = 1001_2 \implies$ bucket 01, $b_3=0$

  • $5 = 0101_2 \implies$ bucket 01, $b_3=1, b_4=0$

  • $13 = 1101_2 \implies$ bucket 01, $b_3=1, b_4=1$

  • Keys $5$ and $13$ share $b_3=1$ and split on $b_4$, which perfectly matches the given tree at bucket 01.

  • Bucket 00 remains empty.

  Thus, (C) is correct.

• Option (D): Keys $\{9, 5, 13, 6, 10, 14\}$

  • $6 = 0110_2$, $10 = 1010_2$, and $14 = 1110_2$ all hash to bucket 10, requiring 3 keys and another split at 10, which does not match the diagram. Thus, (D) is incorrect.

Therefore, only (C) produces the given state.