A compressed trie

Write a compressed trie (lesson 4): each edge carries a string, the labels below a node start with different letters, and every node except the root is the end of a word or has at least two children. Store edges as the starter does: node.kids maps the first letter of a label to the pair (label, child). insert, search and starts_with work as in TRIE-P1.

The method labels() is given. It lists the edge labels depth first, in alphabetical order, so the tests can see the shape of your trie.

t = RadixTrie()
for w in ["bus", "tea", "team", "ten", "to", "toast"]:
    t.insert(w)
t.labels()
# ['bus', 't', 'e', 'a', 'm', 'n', 'o', 'ast']
t.starts_with("toa")   # True: ends inside the edge 'ast'
t.search("toa")        # False

Words and prefixes are non-empty and use the letters a to z. The same word may be inserted twice.

Limits

• Up to 20,000 words of at most 8 letters. Each operation should take O(L) time, and the trie must have at most 2n nodes for n different words.