Prefix Trees

Tries (Prefix Trees)

The ultimate structure for string search and autocomplete. Store words character by character for blazing fast prefix lookups in O(L) time.

Core Mechanics

A Trie is a tree where each node represents a single character. Paths down the tree form words.

TrieNode
Contains a dictionary/array mapping characters to child nodes, and a boolean is_word flag.
Insert
Iterate through the string. If a character isn't a child, create a new node. Mark the final node's is_word = True.
Search & StartsWith
Traverse the tree. If you run out of nodes before finishing the word, return False. For exact search, return is_word at the end.

Time Complexity: O(L) for insert/search, where L is the length of the word.

Trie Template

class TrieNode:
    def __init__(self):
        self.children = {}  # char -> TrieNode
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        curr = self.root
        for char in word:
            if char not in curr.children:
                curr.children[char] = TrieNode()
            curr = curr.children[char]
        curr.is_word = True

    def search(self, word: str) -> bool:
        curr = self.root
        for char in word:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return curr.is_word

    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        for char in prefix:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return True

LeetCode Problems

  • MediumImplement Trie (Prefix Tree)Standard Template
  • MediumDesign Add and Search Words Data StructureTrie with DFS for '.' wildcard
  • MediumReplace WordsPrefix matching
  • HardWord Search IITrie + Backtracking on Grid