In the example of Figure 28.1, all keys have the same number of digits (i.e., 9).
In many applications, however, diﬀerent keys have diﬀerent length. This does not pose a problem unless one key is a preﬁx of another (for example, 27 is a preﬁx of 276). For applications in which one key may be a preﬁx of another, we normally add a special digit (say #) at the end of each key. Doing this ensures that no key is a preﬁx of another.
To see why we cannot permit a key that is a preﬁx of another key, consider the example of Figure 28.1. Suppose we are to search for an element with the key 27. Using the search strategy just described, we reach the branch node E. What do we do now? There is no next digit in the search key that can be used to reach the terminating condition (i.e., you either fall oﬀ the trie or reach an element node) for downward moves. To resolve this problem, we add the special digit # at the end of each key and also increase the number of children ﬁelds in an element node by one. The additional child ﬁeld is used when the next digit equals #.
An alternative to adding a special digit at the end of each key is to give each node a data ﬁeld that is used to store the element (if any) whose key exhausts at that node. So, for example, the element whose key is 27 can be stored in node E of Figure 28.1. When this alternative is used, the search strategy is modiﬁed so that when the digits of the search key are exhausted, we examine the data ﬁeld of the reached node. If this data ﬁeld is empty, we have no element whose key equals the search key. Otherwise, the desired element is in this data ﬁeld.
It is important to note that in applications that have diﬀerent length keys with the property that no key is a preﬁx of another, neither of just mentioned strategies is needed; the scheme described in Section 28.2 works as is.