when items are inserted into the trie sentinel unit is added in the case of the spell checkera '$character is appended to the end of every word the sentinel is needed because words like rat are prefixes to words like ratchet without the sentinel character it would be unclear whether word ended or was only prefix of some other word in trie keys with common prefix share that prefix and are not repeated the next pointer is used when more than one possible next character is possible this saves space in the data structure the trade-off is that the next and follows pointers take extra space in each node the trie class class triedef __insert(node,item)this is the recursive insert function def __contains(node,item)this is the recursive membership test class trienodedef __init__(self,item,next nonefollows none)self item item self next next self follows follows def __init__(self)self start none def insert(self,item)self start trie __insert(self start,item def __contains__(self,item)return trie __contains(self start,iteminserting into trie inserting values into trie can be done either iterativelywith loopor recursively to recursively insert into trie the insert method can call an __insert function it is easier to write the recursive code as function and not method of the trie class because the node value passed to the function may be none to insert into the triethe __insert function operates as follows if the key is empty ( no units are left in the key)return none as the empty node if the node is none then new node is created with the next unit of the key and the rest of the key is inserted and added to the follows link this copy belongs to 'acha