How Tries work

Before you start

• Hashing

  Each trie node is a dict from a character to a child. That lesson covers dict lookups.

  Open lesson

Why it matters

Autocomplete, spell checking, and command palettes all ask whether a string or prefix exists inside a large changing dictionary. Scanning every stored word makes response time grow with the collection even when the query is short. Exact-word and prefix queries must depend on the query's length, not on the number of stored words.

Implement a trie with insert, search (whole word), and startsWith (prefix). Tests call trie(ops, args).

Input

operations = ["Trie", "insert", "search", "search", "startsWith", "insert", "search"], arguments = [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output

[None, None, True, False, True, None, True]

After insert("apple"), a list-based search still scans stored words for "app". Follow the shared a → p → p path instead: its missing end mark makes search("app") False, while startsWith("app") is True, independent of dictionary size.

insert("apple") starts at the empty root and creates the path a → p → p → l → e. The final e node receives a "$" mark. search("apple") follows all five edges and finds that mark, so it returns True.

search("app") reaches the second p but initially finds no "$", so it returns False; startsWith("app") returns True because the path exists. insert("app") adds only the missing end mark at that p. The final search("app") then returns True without changing the shared "apple" path.