Example: Building Step by Step

Array: $[3, 1, 4, 1, 5, 9, 2, 6]$, alphabet $[1, 9]$. Root (values 1-9, mid=5):

• Bitvector: values $\leq 5$ get 0, values $> 5$ get 1
• Array: $[3, 1, 4, 1, 5, 9, 2, 6]$
• Bits: $[0, 0, 0, 0, 0, 1, 0, 1]$
• Left gets: $[3, 1, 4, 1, 5, 2]$
• Right gets: $[9, 6]$

Left child (values 1-5, mid=3):

• Array: $[3, 1, 4, 1, 5, 2]$
• Bits: $[0, 0, 1, 0, 1, 0]$
• Left: $[3, 1, 1, 2]$, Right: $[4, 5]$

Continue recursively until each node handles a single value.