Prefix Tree Insertion & Lookup

Foundations

A trie, or prefix tree, stores strings by their characters. Each node holds a map from a character to a child node, so every edge spells one character and a path from the root spells a prefix. A flag on a node, isEnd, marks where an inserted word ends; the code here stores it as a "$" key. Words that share a prefix share its nodes, so a common start is stored once.

Insert walks the word from the root, creating any missing child, and sets isEnd on the last node. Lookup walks the same way and fails at the first missing edge. A word is present only if the walk ends on an isEnd node, while a prefix only needs the walk to succeed. Each step is one map lookup, so both cost O(L) for a word of length L, however many words are stored.

Insert words = ["to", "tea", "ten", "inn"]: t is shared by three words, and e by tea and ten, so the trie has 8 nodes besides the root instead of 11 letters. Looking up ten walks t, e, n and ends on an isEnd node: found. Looking up te stops on e, which has no isEnd: a prefix, not a word.

• Hashing

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

  Open lesson

Case Scenario

Implement Trie (Prefix Tree) asks for exactly these operations: insert, search for a whole word, and startsWith for a prefix. In the example, after insert("apple"), search("app") is False because the second p has no end mark, while startsWith("app") is True; once insert("app") sets that mark, search("app") becomes True.

The direct approach keeps the words in a list. Inserting is instant, but search and startsWith compare the query with every stored word: O(n · L) for n words. Autocomplete over a million words would scan a million entries per keystroke, though a query of a few letters can only match words that start with those letters.