Implement Trie (Prefix Tree)

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

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 (i.e., was inserted before), 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.

Example 1:

Input [“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”] [[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]] Output [null, null, true, false, true, null, true]

Explanation Trie trie = new Trie(); trie.insert(“apple”); trie.search(“apple”); // return True trie.search(“app”); // return False trie.startsWith(“app”); // return True trie.insert(“app”); trie.search(“app”); // return True

Constraints:

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

Approach: Array-Based Trie Nodes

Algorithm

1. Each TrieNode holds an array of 26 child pointers (one per lowercase letter) and a boolean isEnd
2. insert: walk through the word, creating nodes as needed; mark the final node as the end of a word
3. search: walk through the word; if any child is missing return false; at the end return isEnd
4. startsWith: same walk as search but returns true as long as the prefix exists

Time & Space Complexity

• Time Complexity: O(L) for each operation, where L is the length of the word/prefix
• Space Complexity: O(N * L) in the worst case - N words of average length L; each node holds a 26-element array

Java Implementation

public class Trie {

    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    private final TrieNode root;

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

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

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

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

    private TrieNode findNode(String s) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }

    // Test method
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));    // return true
        System.out.println(trie.search("app"));      // return false
        System.out.println(trie.startsWith("app"));  // return true
        trie.insert("app");
        System.out.println(trie.search("app"));      // return true
    }
}

Example Walkthrough

Inserting “apple” and “app”:

1. Insert “apple”: create nodes for a -> p -> p -> l -> e, mark e as end
2. search("apple"): walk down and find e with isEnd = true -> true
3. search("app"): walk to the second p, its isEnd is false -> false
4. startsWith("app"): the node exists -> true
5. Insert “app”: reuse existing nodes, mark the second p as end
6. search("app"): isEnd is now true -> true

Key Points

1. Shared Prefixes: Words share common prefixes, keeping storage compact
2. 26-Child Array: Fast O(1) child lookup by subtracting 'a'
3. isEnd Flag: Distinguishes a prefix from a complete word for search
4. StartsWith: Only needs the node to exist, not to be a word end
5. Character Set: Works because words contain only lowercase English letters