Exercises

1. Write an algorithm that prints out all of the keys stored in a trie. Not counting the action of printing each key, it should run in time O(n), where n is the number of nodes in the trie. (Printing the keys will require time O(L), where L is the total length of all of the keys.) An auxillary data structure can be used, but its size must not be greater than O(l), where l is the length of the longest key in the trie.
2. Using a patricia, as described in this chapter, show that inserting a new key can cause at most one node to be uncollapsed, and that the deletion of one key can cause at most one node to be collapsed.
3. Write an algorithm that takes a key k and finds all the keys in a trie that differ from k in exactly one character position. The algorithm should run in time O(l), where l is the length of the key, and be independent of the number of keys in the trie.

   There are, of course, only O(l) such keys possible, so a time complexity of O(l) should be the worst case. Your goal is to rule out as many possibilities as you can as early as possible.

4. What is the time complexity of using a trie to sort a set of keys? (Hint- first choose how to measure the the ``size'' of the problem.)