Given two strings a = a0a1. . .ap and b = b0b1. . .bq, where each ai and each bj is in some ordered set of characters, we say that string a is lexicographically less than string b if either A. there exists an integer j,0?j?min(p,q), such that ai =bi for all i=0, 1, . . . , j - 1 and aj bj, or B. pq and ai = bi for all i = 0, l, . . . , p. For example, if a and b are bit strings, then 10100 j = 3) and 10100 a=a0a1 ...ap,we go left at a node of depth i if ai =0and right if ai =1. Let S be a set of distinct binary strings whose lengths sum to n.

Show how to use a radix tree to sort S lexicographically in O(n) time. For the example in Figure 1, the output of the sort should be the sequence 0, 011, 10, 100, 1011.

Figure 1 A radix tree storing the bit strings 1011, 10, 011, 100, and 0. Each nodes key can be determined by traversing the path from the root to that node. There is no need, therefore, to store the keys in the nodes; the keys are shown here for illustrative purposes only. Nodes are heavily shaded if the keys corresponding to them are not in the tree; such nodes are present only to establish a path to other nodes.