Implement Trie (Prefix Tree)

Problem Description

A trie or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie, and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Examples

Constraints

• 1 ≤ word.length, prefix.length ≤ 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 10⁴ calls in total will be made to insert, search, and startsWith.

Trading Fan-Out Space for Prefix Match Speed

Using a hash set or list to store words makes prefix searches slow. To see if a prefix exists in a hash set, you have to scan all strings, which is O(n * k) where n is the number of words and k is the length. A trie resolves this by nesting characters as tree nodes.

Each node contains an array of size 26 (for lowercase English letters) pointing to child nodes, and a boolean flag marking if the node completes a word. To insert or search, you follow the character pointers down the tree. A search succeeds if you trace all characters and end on a node marked as a word. A prefix search succeeds if you can trace all characters, regardless of the word end flag.

Solution 1: Array-Based Trie Nodes

Use a 26-element array inside each node to represent children pointers for lowercase ASCII characters.

class Trie {
    private class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord = false;
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) {
                curr.children[idx] = new TrieNode();
            }
            curr = curr.children[idx];
        }
        curr.isWord = true;
    }

    public boolean search(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) return false;
            curr = curr.children[idx];
        }
        return curr.isWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) return false;
            curr = curr.children[idx];
        }
        return true;
    }
}

class TrieNode:
    def __init__(self):
        self.children = {}  # maps char -> TrieNode
        self.is_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.is_word = True

    def search(self, word: str) -> bool:
        curr = self.root
        for c in word:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return curr.is_word

    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        for c in prefix:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return True

class Trie {
private:
    struct TrieNode {
        TrieNode* children[26] = {};
        bool isWord = false;
    };
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(std::string word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->children[idx]) {
                curr->children[idx] = new TrieNode();
            }
            curr = curr->children[idx];
        }
        curr->isWord = true;
    }

    bool search(std::string word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->children[idx]) return false;
            curr = curr->children[idx];
        }
        return curr->isWord;
    }

    bool startsWith(std::string prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!curr->children[idx]) return false;
            curr = curr->children[idx];
        }
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(L) for all operations, where L is the length of the word or prefix. We perform at most L lookups/insertions.
• Space Complexity: O(N * L) where N is the number of words and L is the average length. In the worst case (no shared prefixes), every character requires a new node.

Where it breaks: If you insert a very large number of distinct short words, the memory usage can explode because each node allocates a 26-element array, even if only one child is used. A hash map for children nodes (as done in Python above) can reduce this sparse array overhead.

Why Not Use a Binary Search Tree of Strings?

A balanced binary search tree of strings would achieve O(L * log N) time complexity for search operations. A trie runs in O(L) time, which is independent of the number of elements in the trie. The speed benefit becomes significant when N is in the millions.

Common Mistakes

• Forgetting to set isWord = true at the end of insertion. If you omit this, search will return false for exact word matches because the node won’t be marked as completing a word.
• Using a generic nested dictionary structure in Python without clear object types. While children = {} is valid, defining a clear node structure prevents mistakes in more complex trie problems.
• Not validating characters. This implementation assumes lowercase English letters. If input contains uppercase characters or symbols, array indexing c - 'a' will cause out of bounds errors.

Frequently Asked Questions

How does a Trie compare to a Hash Map for word lookup? A hash map has O(1) average time but O(L) worst-case time because computing the hash of a string requires reading all L characters. A trie also runs in O(L) time but naturally supports prefix matching, which a hash map cannot do efficiently.

Can you delete words from a Trie? Yes. To delete, you search for the word, set isWord = false, and then recursively delete nodes bottom-up if they have no other children and do not mark the end of another word.

What does this problem test in interviews? It tests basic object-oriented design, custom tree node structures, pointer manipulation, and understanding the trade-off between lookup speed and memory overhead.

← All Problems