membership structures if the first unit of the key matches the unit of the current nodethen the rest of the key is inserted into the follows link of the node otherwisethe key is inserted into the next link of the node building the trie recursively is simple howeveran iterative version would work just as well the iterative version would require loop and pointer to the current node along with remaining key to insert the iterative insert algorithm would behave in similar fashion to the step outlined above but would need to keep track of the previous node as well as the current node so that links could be set correctly membership in trie checking membership in trie can also be accomplished recursively the steps include base case which might not be completely intuitive at first the empty key is reported as member of any trie because it works when checking membership with the sentinel unit added to the triereturning true for an empty key is completely safe because any real key will at least consist of the sentinel character in the algorithm outlined here the sentinel is assumed to have already been added to the key the steps for membership testing are as follows if the length of the key is then report success by returning true if the node we are looking at is none then report failure by returning false if the first unit of the key matches the unit in the current nodethen check membership of the rest of the key starting with the follows node otherwisecheck membership of the key starting with the next node in the trie againthis code might be implemented iteratively with while loop keeping track of the current node and the remainder of the key either recursive or iterative implementation will work equally well comparing tries and bloom filters bloom filters are clearly faster for testing membership than trie howeverthe trie works acceptably well while the longest bloom filter lookup time in simple experiment was usthe longest trie lookup was us of course the trie takes more spacebut common prefixes share nodes in trie saving some space over storing each word distinctly in data structureas in hash set for purposes of spell checking trie has distinct advantagessince spelling alternatives can be easily found common typographical errors fall into one of four categories this copy belongs to 'acha