__Searching a Trie__

To search a trie for an element with a given key, we start at the root and follow a path down the trie until we either fall oﬀ the trie (i.e., we follow a *null *pointer in a branch node) or we reach an element node. The path we follow is determined by the digits of the search key. Consider the trie of Figure 28.1. Suppose we are to search for an element with key 951-23-7625. We use the ﬁrst digit, 9, in the key to move from the root node *A *to the node *A.c**hild*[9] = *D*. Since *D *is a branch node, we use the next digit, 5, of the key to move further down the trie. The node we reach is *D**.child*[5] = *F *. To move to the next level of the trie, we use the next digit, 1, of the key. This move gets us to the node *F**.child*[1] = *I*. Once again, we are at a branch node and must move further down the trie. For this move, we use the next digit, 2, of the key, and we reach the element node *I**.child*[2] = *J *. When an element node is reached, we compare the search key and the key of the element in the reached element node. Performing this comparison at node *J *, we get a match. The element in node *J *, is to be returned as the result of the search.

When searching the trie of Figure 28.1 for an element with key 951-23-1669, we follow the same path as for the key 951-23-7625. The key comparison made at node *J *tells us that the trie has no element with key 951-23-1669, and the search returns the value *null*.

To search for the element with key 562-44-2169, we begin at the root *A *and use the ﬁrst digit, 5, of the search key to reach the element node *A.c**hild*[5] = *C*. The key of the element in node *C *is compared with the search key. Since the two keys agree, the element in node *C *is returned.

When searching for an element with key 273-11-1341, we follow the path *A**, A.child*[2] = *B**, B.child*[7] = *E**, E.child*[3] = *null*. Since we fall oﬀ the trie, we know that the trie contains no element whose key is 273-11-1341.

When analyzing the complexity of trie operations, we make the assumption that we can obtain the next digit of a key in *O*(1) time. Under this assumption, we can search a trie for an element with a *d *digit key in *O*(*d*) time.