Implement Trie (Prefix Tree)

Medium Tries Basics Original on LeetCode

Implement Trie (Prefix Tree) is a medium tries problem solved with the basics pattern. The best approach, optimal (trie nodes with 26 children), runs in O(L) per operation time and O(total characters · 26) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from hash set of words up.

Problem

Implement a trie (prefix tree) with three operations: insert(word), search(word) (was this exact word inserted?) and startsWith(prefix) (was any word with this prefix inserted?).

Examples

Example 1

Input
insert("apple"); search("apple"); search("app"); startsWith("app"); insert("app"); search("app")
Output
true, false, true, true

Constraints

  • Words and prefixes use lowercase letters, length 1 to 2000.
  • Up to 3 * 10^4 calls.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (1 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Hash set of wordsO(n · L) for startsWithO(total characters)
Optimal (trie nodes with 26 children)O(L) per operationO(total characters · 26)

1Hash set of words

TimeO(n · L) for startsWith
SpaceO(total characters)

Store the words in a set. search is O(L) on average, but startsWith must scan every word.

  1. insert: add to set. search: contains.
  2. startsWith: check each word's prefix.
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;
    }
}

2Optimal (trie nodes with 26 children)

TimeO(L) per operation
SpaceO(total characters · 26)

Walk down one node per character, creating nodes on insert. search needs the walk to succeed and the final node to be marked as a word end; startsWith only needs the walk to succeed.

  1. insert: for each char, create the child if missing; move; mark end.
  2. search: walk; return node != null && node.end.
  3. startsWith: walk; return node != null.
class Trie {
    private static class Node {
        Node[] next = new Node[26];
        boolean end;
    }

    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.end = true;
    }

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

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

    private Node walk(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.next[c - 'a'];
            if (cur == null) return null;
        }
        return cur;
    }
}

Edge cases to test

  • A word that is a prefix of another (app vs apple)
  • search for a prefix that exists but is not a full word

Hints

Hint 1

Each node has 26 child slots and a flag that marks the end of a word.

FAQ

What is the best time complexity for Implement Trie (Prefix Tree)?

Optimal (trie nodes with 26 children) runs in O(L) per operation time and O(total characters · 26) extra space.

Which pattern does Implement Trie (Prefix Tree) use?

It is a tries problem that uses the basics pattern. Other problems with the same pattern: Implement Trie ll, Design In-Memory File System, Design Search Autocomplete System.

Is there a brute force solution for Implement Trie (Prefix Tree)?

Yes. Hash set of words takes O(n · L) for startsWith time and O(total characters) space. Store the words in a set.

Which edge cases should I test for Implement Trie (Prefix Tree)?

A word that is a prefix of another (app vs apple); search for a prefix that exists but is not a full word.