Implement Trie (Prefix Tree)

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Build a trie (prefix tree) class with three methods: insert(word) adds a word, search(word) returns true if that exact word was inserted, and startsWith(prefix) returns true if any inserted word begins with the prefix. Words use lowercase English letters.

    This is the "build the data structure" question behind every autocomplete and word-puzzle problem. Interviewers use it as a warm-up or as the first half of a harder question such as Word Search II. Original problem: LeetCode 208.

    Example

    After inserting "apple", searching "apple" is true, searching "app" is false because no word ends at the second p, and startsWith("app") is true. Once "app" is inserted, searching it returns true.
    After inserting "apple", searching "apple" is true, searching "app" is false because no word ends at the second p, and startsWith("app") is true. Once "app" is inserted, searching it returns true.
    insert("apple")
    search("apple")      -> true
    search("app")        -> false   # only a prefix so far
    startsWith("app")    -> true
    insert("app")
    search("app")        -> true

    Constraints (assumed)

    • 1 ≤ word and prefix length ≤ 2,000.
    • Only lowercase letters a–z.
    • Up to 30,000 calls in total.

    What this question tests

    • Designing a small node structure and choosing between a 26-slot array and a hash map for the children.
    • Telling apart "this path exists" and "a word ends here".
    • Clean class design with a shared helper instead of three copies of the same loop.

    Questions to ask first

    1. What characters can appear? Lowercase only allows a fixed 26-slot array; Unicode needs a map.
    2. Will we need delete? It changes what each node stores (often a count of words passing through).
    3. Is memory or speed more important? Arrays are faster, maps use less memory for sparse tries.
    4. Should search("") or startsWith("") be supported? With this design, startsWith("") is true and search("") is false unless the empty word was inserted.