Implement Trie (Prefix Tree)

MediumTrie · Design🧩 Trie LeetCode #208 ↗Updated Oct 30, 2026

Problem

Build a Trie class for lowercase words with three operations: insert(word) stores a word, search(word) tells whether that exact word was inserted, and startsWith(prefix) tells whether any inserted word begins with the given prefix.

Inputinsert("apple") search("apple")Outputtrue

Inputsearch("app") startsWith("app")Outputfalse, true

Inputinsert("app") search("app")Outputtrue

1 ≤ word.length, prefix.length ≤ 2000 · lowercase letters only · ≤ 3·10⁴ calls in total

Try it yourself

Java

class Trie {
    public void insert(String word) {
        
    }

    public boolean search(String word) {
        
    }

    public boolean startsWith(String prefix) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Words that share a prefix should share storage. A tree where each edge is a letter makes every prefix a single path from the root, so all three operations just walk L steps — independent of how many words are stored.

PatternTrie

Instinct Many words, shared prefixes, and questions like "starts with", autocomplete, wildcard match or "search a board for all these words" - build a prefix tree.

Memory hack Words share their beginnings, so store each beginning once - walk one letter per step, and an end flag marks where a real word stops.

Open the Trie guide →

Approaches

Brute ForceHashSet + Linear Prefix Scan

Time O(L) insert/search, O(N·L) startsWithSpace O(S)

A HashSet answers exact lookups in O(L) (hashing the word). For startsWith there is no shortcut: test every stored word with String.startsWith. N = words stored, S = total characters.

Java

class Trie {
    private final Set<String> words = new HashSet<>();

    public void insert(String word) { words.add(word); }

    public boolean search(String word) { return words.contains(word); }

    public boolean startsWith(String prefix) {
        for (String w : words) {
            if (w.startsWith(prefix)) return true;
        }
        return false;
    }
}

Exact search is fast, but prefix queries degrade linearly with N.

BetterSorted Set (TreeSet) + ceiling

Time O(L log N) all opsSpace O(S)

In sorted order, all words with a given prefix form a contiguous block that starts at the smallest word ≥ the prefix. So ceiling(prefix) is the only candidate to check. Each comparison costs up to O(L), and the tree has depth O(log N).

Java

class Trie {
    private final TreeSet<String> words = new TreeSet<>();

    public void insert(String word) { words.add(word); }

    public boolean search(String word) { return words.contains(word); }

    public boolean startsWith(String prefix) {
        String next = words.ceiling(prefix);   // smallest word >= prefix
        return next != null && next.startsWith(prefix);
    }
}

Logarithmic prefix queries with library code, but still pays string compares.

OptimalTrie with children[26]

Time O(L) all opsSpace O(26·S)

Each node holds 26 child pointers and an isEnd flag. Insert creates missing nodes along the path and marks the last one; search and startsWith walk the same path. The only difference: search also needs isEnd, while startsWith just needs the path to exist.

Java

class Trie {
    private static class Node {
        Node[] next = new Node[26];
        boolean isEnd;
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
            cur = cur.next[c - 'a'];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        Node node = walk(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) { return walk(prefix) != null; }

    private Node walk(String s) {   // node at the end of s's path, or null
        Node cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.next[c - 'a'];
            if (cur == null) return null;
        }
        return cur;
    }
}

O(L) per op regardless of N — the canonical answer.

Pro tip

For large or unknown alphabets use Map<Character, Node> children — same O(L), far less memory per node.

At a glance

Level	Approach	Time	Space
Brute Force	HashSet + Linear Prefix Scan	`O(L) insert/search, O(N·L) startsWith`	`O(S)`
Better	Sorted Set (TreeSet) + ceiling	`O(L log N) all ops`	`O(S)`
Optimal	Trie with children[26]	`O(L) all ops`	`O(26·S)`

Common pitfalls

Returning true from search just because the path exists — check isEnd.
Allocating a new node on every insert step — overwrites existing subtrees.
Sharing one helper for search/startsWith but forgetting their end conditions differ.

Interview tips

Clarify the alphabet: fixed 26 letters → array; Unicode → hash map.
Factor the common path walk into one helper to avoid duplicated loops.
Discuss memory: 26 pointers per node vs sharing of common prefixes.

Pattern

Trie → many prefix lookups over a dictionary of strings (autocomplete, word search).

My notes saved in this browser