Trie bug hunt

Questions 1 to 5 of 8

1. 1. This insert is used for a trie whose nodes hold children, a list of 26 slots, and a boolean is_end. ``python def insert(root, word): node = root for ch in word: idx = ord(ch) - ord("a") if node.children[idx] is None: node.children[idx] = Node() node = node.children[idx] ` After insert(root, "cat"), search(root, "cat") returns False`. What is the bug?

   The index ord(ch) - ord("a") puts the letters in the wrong slotsThe loop should start at index 1, so the first letter is not skippedinsert never sets is_end to True on the node for the last lettersearch should call starts_with, which reads the end flag
2. 2. What does this program print? ``python def index(ch): return ord(ch) - ord("a") + 1 print(index("a"), index("z")) ``

   0 261 260 251 25
3. 3. This index function is used for a list of 26 children and lowercase words. ``python def index(ch): return ord(ch) - ord("A") ` Inserting cat raises IndexError: list index out of range`. What is the bug?

   The list should have 52 slots, because lowercase and uppercase letters both need oneThe method subtracts ord("A") (65), so the lowercase c (99) gives 34, which is past the end of a 26-slot listThe loop reads each character as a whole string, so index gets the wrong typeThe index is taken from the position in the word, not from the letter
4. 4. Which check finds the missing end flag bug in a trie?

   Insert a word, then search for that same word, and expect TrueSearch for a word that was never inserted, and expect FalsePrint the number of nodes after inserting one wordCall starts_with only, because it reads the end flag
5. 5. insert and search both use this index function with a list of 26 children. ``python def index(ch): return ord(ch) - ord("a") + 1 ` Words like cat and dog work, but zoo raises IndexError: list index out of range`. What is the bug?

   Both words share one list slot, so zoo overwrites catThe letter z has the code 122, so the subtraction gives a value that is too large for any listThe + 1 pushes z, which would be index 25, to index 26, which is past the end of a 26-slot listIndex 0 is reserved for a, so zoo has no free slot