Given two strings a = a₀a₁ . . .a_p and b = b₀b₁ . . .b_q, where each a_i and each b_j is in some ordered set of characters, we say that string a is lexicographically less than string b if either 

1. there exists an integer j, where 0 ≤ j ≤ min(p, q), such that a_i = b_i for all i = 0, 1, . . . , j – 1 and a_j < b_j, or

2. p < q and a_i = bi for all i = 0, 1, . . . , p.

For example, if a and b are bit strings, then 10100 < 10110 by rule 1 (letting j = 3) and 10100 < 101000 by rule 2. This ordering is similar to that used in English-language dictionaries.

The radix tree data structure shown in Figure 12.5 stores the bit strings 1011, 10, 011, 100, and 0. When searching for a key a = a₀a₁ . . .a_p, we go left at a node of depth i if a_i = 0 and right if a_i = 1. Let S be a set of distinct bit strings whose lengths sum to n. Show how to use a radix tree to sort S lexicographically in Θ(n) time. For the example in Figure 12.5, the output of the sort should be the sequence 0, 011, 10, 100, 1011.