Trie Implementation and Operations

Hard TUF ID 1028 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Design a data structure that stores a collection of words and supports three operations:

insert(word) adds word to the collection.
search(word) returns true if word itself was inserted earlier.
startsWith(prefix) returns true if at least one inserted word begins with prefix.

The structure you are expected to build is the trie (pronounced “try”, also called a prefix tree). This row is the theory lecture for the whole trie section, so the article also explains how a trie is laid out; every later problem in the section reuses the class written here.

Constraints (LeetCode 208): words and prefixes are non-empty strings of lowercase English letters, at most 2000 characters long, and there are at most 3 × 10^4 calls in total.

Example 1

insert("apple")
search("apple")      -> true
search("app")        -> false    // "app" is only a prefix of a stored word
startsWith("app")    -> true
insert("app")
search("app")        -> true     // now it is a word in its own right

Example 2

insert("striver"), insert("strike")
search("stri")       -> false    // nobody inserted "stri" as a word
startsWith("stri")   -> true     // both words begin with it
startsWith("strix")  -> false

All three designs below implement one interface, so the Java file can run the same script of operations against each of them and compare the outputs:

interface WordStore {
    void insert(String word);
    boolean search(String word);
    boolean startsWith(String prefix);
}

Approach 1: Brute force, a list of words

Intuition. The simplest thing that works is to remember every word in a list and answer each question by looking at all of them. search asks “is any stored word equal to this one?” and startsWith asks “does any stored word begin with this?”. Both are a single loop with a string comparison. Inserting is free, but every query pays for the whole collection, which is exactly the wrong trade for a dictionary or an autocomplete box that is built once and queried on every keystroke.

Algorithm.

insert: append the word to the list.
search: scan the list and return true on the first word that equals the query.
startsWith: scan the list and return true on the first word for which w.startsWith(prefix) holds.

static class ListStore implements WordStore {
    private final List<String> words = new ArrayList<>();

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

    public boolean search(String word) {
        for (String w : words) {
            if (w.equals(word)) return true;
        }
        return false;
    }

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

Complexity. insert is O(1) amortised. search and startsWith are O(n · L), where n is the number of stored words and L the query length, because each comparison can read up to L characters. Space is O(total characters).

Approach 2: Better, hash sets of words and of prefixes

Intuition. A hash set answers “have I seen this exact string?” in O(L) time on average (hashing a string reads it once). That fixes search immediately: keep the words in a HashSet. For startsWith we need a different question, “is this string a prefix of some word?”, and a set of words cannot answer it. But we can precompute the answer: when a word is inserted, also put every prefix of it into a second set. Then startsWith(p) is a single lookup, because p is a prefix of a stored word exactly when it was added to that set.

Algorithm.

insert(word): add word to words; for len = 1..L add word.substring(0, len) to prefixes.
search(word): return words.contains(word).
startsWith(prefix): return prefixes.contains(prefix).

static class PrefixSetStore implements WordStore {
    private final Set<String> words = new HashSet<>();
    private final Set<String> prefixes = new HashSet<>();

    public void insert(String word) {
        words.add(word);
        for (int len = 1; len <= word.length(); len++) {
            prefixes.add(word.substring(0, len));      // each prefix is a fresh copy of len characters
        }
    }

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

    public boolean startsWith(String prefix) {
        return prefixes.contains(prefix);
    }
}

Complexity. insert is O(L^2): there are L prefixes of lengths 1..L, and each one is copied and hashed. search and startsWith are O(L) on average. Space is O(L^2) characters per word.

That space bill is the real problem. Inserting "apple" stores "a", "ap", "app", "appl" and "apple" as five separate strings, although they are all made of the same five characters, and a single 2000-letter word stores about two million characters of prefixes. Words that share a beginning, such as "apple" and "apply", duplicate it again. The trie removes all of this duplication by storing each distinct prefix exactly once, as a node.

How a trie is organised

A trie is a rooted tree in which every node stands for one prefix: the string you read by following edges from the root down to it. The root is the empty prefix. Each node has up to 26 children, one per letter that can come next, and a boolean isEnd that says whether some inserted word ends exactly at this node. Here is the trie after inserting "apple", "app" and "bat":

(root)
 ├─ a
 │  └─ p
 │     └─ p        isEnd  ("app")
 │        └─ l
 │           └─ e  isEnd  ("apple")
 └─ b
    └─ a
       └─ t        isEnd  ("bat")

Three facts make every operation easy:

Shared prefixes are shared nodes. "app" and "apple" use the same first three nodes. The total number of nodes is at most one plus the total number of inserted characters, and usually far fewer.
A path exists exactly when some word has that prefix. Nodes are only ever created by insert, so if the walk for "ap" reaches a node, some inserted word passed through it.
isEnd separates words from mere prefixes. The nodes for "ap" and "app" both exist, but only the second carries the flag, so only "app" is a word.

Children live in an array indexed by c - 'a', which gives O(1) access with no hashing. The price is 26 references per node even when most are null. For a large alphabet (Unicode, mixed case, digits) a HashMap<Character, Node> per node is the usual substitute.

Approach 3: Optimal, the trie

Intuition. Every operation is a walk from the root, one letter at a time. insert walks and creates any edge that is missing, then sets the flag on the last node. search walks and needs both the full path and the flag. startsWith walks and needs only the path. Each step is an array lookup, so the cost depends only on the length of the string, never on how many words are stored.

Algorithm.

insert(word): start at the root. For each letter c, create child[c] if it is null, then move to it. Finally set isEnd = true on the node reached.
walk(s): start at the root and follow each letter; return null as soon as an edge is missing, otherwise the final node.
search(word): walk(word) must be non-null and have isEnd set.
startsWith(prefix): walk(prefix) must be non-null.

static class Trie implements WordStore {
    private static class Node {
        final Node[] child = new Node[26];             // child[c - 'a'] is the edge labelled c
        boolean isEnd;                                 // some inserted word ends exactly here
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (cur.child[c] == null) cur.child[c] = new Node();   // create the edge only when it is missing
            cur = cur.child[c];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        Node node = walk(word);
        return node != null && node.isEnd;             // the path must exist AND a word must end on it
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;                   // the path existing is enough
    }

    /** Follows s from the root; returns the node reached, or null as soon as a letter has no edge. */
    private Node walk(String s) {
        Node cur = root;
        for (int i = 0; i < s.length(); i++) {
            cur = cur.child[s.charAt(i) - 'a'];
            if (cur == null) return null;
        }
        return cur;
    }
}

Dry run on Example 1:

Operation	Path walked	Nodes created	Result
`insert("apple")`	a, p, p, l, e	5	flag set on `e`
`search("apple")`	a, p, p, l, e	0	node found, flag set: `true`
`search("app")`	a, p, p	0	node found, flag not set: `false`
`startsWith("app")`	a, p, p	0	node found: `true`
`insert("app")`	a, p, p	0	flag set on the second `p`
`search("app")`	a, p, p	0	node found, flag set: `true`

Complexity. Every operation is O(L) time, one array access per character. Space is O(N · 26) references in the worst case, where N is the total number of inserted characters, since each character creates at most one node; shared prefixes make it smaller in practice.

	insert	search	startsWith	extra space
List	`O(1)`	`O(n · L)`	`O(n · L)`	words only
Two hash sets	`O(L^2)`	`O(L)`	`O(L)`	`O(L^2)` per word
Trie	`O(L)`	`O(L)`	`O(L)`	one node per new character

Edge cases and pitfalls

search is not startsWith. Forgetting the isEnd check makes search("app") return true after inserting only "apple". That is the single most common trie bug.
Duplicate inserts are harmless: the walk finds every node and sets a flag that is already set. If you need to know how many times a word was inserted, the flag becomes a counter, which is the next problem.
Alphabet assumptions. c - 'a' is only a valid index for lowercase letters; an uppercase letter or digit throws ArrayIndexOutOfBoundsException. Widen the array or switch to a map when the input is not lowercase.
Empty strings. LeetCode never passes one. With this code walk("") returns the root, so startsWith("") is true even on an empty trie, whereas the list version says false. If your variant allows empty strings, decide what they mean and special-case the root.
Iterate, do not recurse. A recursive walk is natural but uses one stack frame per character; the loop has no depth limit.
Memory. Each node is an object plus a 26-slot array, roughly 150 bytes on a 64-bit JVM. A million nodes is on the order of 150 MB, so a trie is fast but not small.

Trie Implementation and Advanced Operations replaces the flag with counters and adds erase.
Longest Word with All Prefixes reads the isEnd flags along a word’s path.
Number of distinct substrings in a string inserts every suffix and counts the nodes created.
Maximum XOR of two numbers in an array builds the same structure over bits instead of letters.
Longest Common Prefix can be answered by walking a trie until it branches.

Trie Implementation and Operations

Problem

Approach 1: Brute force, a list of words

Approach 2: Better, hash sets of words and of prefixes

How a trie is organised

Approach 3: Optimal, the trie

Edge cases and pitfalls

Related problems