Tries (Prefix Trees)

What you'll learn

• What is a Trie?

  A trie (pronounced "try") is a tree-based data structure where each path from the root to a node represents a prefix of one or more stored strings. Unlike binary search trees that store complete keys in each node, a trie distributes a ke…

• Key Insight

  Every descendant of a node shares the same prefix that the path to that node represents. This property makes tries exceptionally powerful for prefix-based operations.

• Node Structure

  Each trie node contains: 1. Children map -- a mapping from characters to child nodes 2. isend flag -- a boolean indicating whether this node marks the end of a complete word There are two common implementations for the children map: | Ap…

• Visualizing a Trie

  Here is a trie storing the words: "app", "apple", "apt", "bat", "bar" Reading paths from root: - root -> a -> p -> p (isend=True) = "app" - root -> a -> p -> p -> l -> e (isend=True) = "apple" - root -> a -> p -> t (isend=True) = "apt" -…

• Operations and Complexity

• Insert -- O(L)

  Where L = length of the word being inserted. Why O(L)? We traverse exactly L levels of the tree, creating one node per character if it does not already exist. Each step is O(1) (dictionary lookup or array index).

• Search -- O(L)

  Why O(L)? We follow the path character by character. If at any point a character is missing from the children, the word does not exist. If we reach the end, we check isend.

• Prefix Search (startsWith) -- O(L)

  Why O(L)? Identical to search, except we do NOT check isend. If we can traverse the entire prefix without hitting a dead end, the prefix exists.

• Delete -- O(L)

  Deletion is the most complex operation. After finding the word, we need to clean up nodes that are no longer part of any other word. Strategy: Use recursion. After marking isend=False, walk back up and remove nodes that: 1. Have no child…

• Space Complexity

  Worst case: O(ALPHABETSIZE L N) Where: - ALPHABETSIZE = number of possible characters (26 for lowercase English) - L = average word length - N = number of words Why? Each node potentially has an array of ALPHABETSIZE pointers, and in t…

• Trie vs Hash Map for String Operations

  | Operation | Trie | Hash Map | |-----------|----------------------------------------|-----------------------------------| | Exact search | O(L) | O(L) average (hashing takes O(L)) | | Prefix search | O(P) where P = prefix length | O(NL)…

• Implementation in Python

• Dictionary-Based (Recommended for Interviews)

• Array-Based (For Fixed Alphabet)

  Why use an array? When the alphabet is small and known (e.g., lowercase English a-z = 26 chars), a fixed-size array gives O(1) child access without hashing overhead and better cache locality. The trade-off is wasted space — every node al…

• Common Patterns

• Pattern 1: Autocomplete / Prefix Matching

  Given a prefix, find all words that start with it. Sample Input / Output Input: dictionary = ["apple", "app", "application"], prefix = "app" Output: ["apple", "app", "application"] (all completions) Input: dictionary = ["apple", "apricot…

• Pattern 2: Word Search in a Grid

  Given a board of characters and a list of words, find all words that can be formed by adjacent cells. Sample Input / Output Input: Output: ["oath", "eat"] Input: Output: [] — cannot reuse cells Input: Output: ["a"] — single cell board ed…

• Pattern 3: Longest Common Prefix

  Find the longest common prefix among a list of strings. Sample Input / Output Input: ["flower", "flow", "flight"] Output: "fl" Input: ["dog", "racecar", "car"] Output: "" (no common prefix) Input: ["interview", "internet", "internal"] Ou…

• Pattern 4: Count Words with Given Prefix

  Extend the trie to count how many words share each prefix. Sample Input / Output Insert: ["apple", "app", "application", "apt", "banana"] Query countPrefix("app") → 3 (apple, app, application) Query countPrefix("ban") → 1 (banana) Query…

• Pattern 5: Replace Words (Dictionary Matching)

  Given a dictionary of roots and a sentence, replace each word with its shortest root. Sample Input / Output Input: dictionary = ["cat", "bat", "rat"], sentence = "the cattle was rattled by the battery" Output: "the cat was rat by the bat…

• When to Use a Trie

  Use a trie when: - You need prefix-based queries (autocomplete, typeahead) - You need to find all strings with a given prefix - You are solving word search / boggle problems - You need sorted iteration of strings - You want guaranteed O(…

• Complexity Summary

  | Operation | Time | Space | |-----------|------|-------| | Insert | O(L) | O(L) new nodes worst case | | Search | O(L) | O(1) | | Prefix search | O(P) | O(1) | | Delete | O(L) | O(1) | | Autocomplete | O(P + KM) | O(KM) for results | |…

• Interview Tips

  1. Default to dict-based nodes in interviews -- less code, handles any character set 2. Always ask about the character set -- lowercase only? ASCII? Unicode? This determines array vs dict 3. Remember isend -- the most common bug is forge…

• Practice Problems Walkthrough

  > These walkthroughs assume the Trie / TrieNode classes defined earlier in Implementation in Python. Markdown does not let you link inside a fenced code block, so a back-link precedes each snippet — click it to scroll back to the class d…

• Problem: Implement a search with wildcards

  Support . as a wildcard that matches any single character (LeetCode 211 — "Design Add and Search Words"). Sample Input / Output Input: words = ["bad", "dad", "mad"], search = ".ad" Output: True (matches bad, dad, mad) Input: words = ["ba…

• Problem: Design a search autocomplete system

  Given a stream of sentences (each with a frequency), and characters typed one at a time by a user, return the top 3 sentences (by frequency, ties broken alphabetically) that start with what the user has typed so far. # ends the query and…

• Key Takeaways

  1. A trie is a tree where each root-to-node path represents a prefix 2. Insert, search, and prefix operations are all O(L) -- proportional to word length, not dataset size 3. Tries excel at prefix-based operations where hash maps struggl…