A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

Chapter 17

These are the solutions to the exercises found in the section ​Exercises​.

1. This trie stores the words: “tag”, “tan”, “tank”, “tap”, “today”, “total”, “we”, “well”, and “went”.

2. Here is a trie that stores the words “get”, “go”, “got”, “gotten”, “hall”, “ham”, “hammer”, “hill”, and “zebra”:

   

3. The following code starts at the trie’s node and iterates over each of its children. For each child, it prints the key and then recursively calls itself on the child node:

   def traverse(self, node=None):
       current_node = node or self.root
   
       for key, child_node in current_node.children.items():
           print(key)
   
           if key != "*":
    self.traverse(child_node) ...