Trie

A trie supports prefix search.

A trie is a tree that stores words by their prefix. Each node represents a letter; the path from root to leaf forms a word.

It is efficient for prefix searches like autocomplete or spell check. Insert and search run in O(L) time; L is word length.

Dictionary structure

Trie nodes are represented as a dictionary. Each node holds a mapping from letter to child node. Word end is marked with '$'.

This representation lets the tree grow automatically as new letters are added. An empty trie starts with {}.

Write init_trie(). Return an empty trie root (dictionary). Print it with print(init_trie()).

Show example solution

def init_trie():
    # Return empty trie root
    return {}
print(init_trie())

Next lesson: Segment tree