How to Implement a Trie (Prefix Tree) for String Searching and Autocomplete

A Trie (prefix tree) stores strings in a tree structure that shares common prefixes, enabling O(L) time complexity for insertions, exact searches, and autocomplete queries where L is the query length.

The kdn251/interviews repository provides complete Java implementations of this essential data structure, which powers search engine autocomplete, spell checkers, and IP routing tables. Learning how to implement a Trie (prefix tree) for string searching and autocomplete requires understanding its node-based architecture, path-sharing mechanics, and traversal algorithms that operate independently of the total stored word count.

Core Trie Architecture in ImplementTrie.java

The foundation of the data structure rests on two primary classes defined in leetcode/trie/ImplementTrie.java: the node container and the public API manager.

The TrieNode Structure

According to lines 11-16 of ImplementTrie.java, each node maintains a HashMap for child edges, a character value, and a completion flag.

class TrieNode {
    HashMap<Character, TrieNode> map; // child edges
    char character;                 // stored character (optional for debugging)
    boolean last;                   // true if this node terminates a word

    public TrieNode(char character) {
        this.map = new HashMap<>();
        this.character = character;
        this.last = false;
    }
}

The HashMap provides O(1) lookup for child nodes, while the boolean last flag distinguishes between mere prefixes and complete words.

The Trie Container Class

The ImplementTrie class (lines 28-84) manages a single root node and exposes three public methods: insert, search, and startsWith. This design keeps the internal pointer manipulation encapsulated while providing a clean interface for string operations.

Implementing Basic Trie Operations

All core methods follow a consistent pattern: iterate through the query string character by character, traversing or creating nodes as needed.

Inserting Words

The insert method walks the tree, creating missing nodes via computeIfAbsent, then marks the final node with last = true.

public void insert(String word) {
    TrieNode current = root;
    for (char c : word.toCharArray()) {
        current.map.computeIfAbsent(c, ch -> new TrieNode(ch));
        current = current.map.get(c);
    }
    current.last = true; // mark end of word
}

This approach ensures O(L) time complexity where L is the word length, as each character triggers exactly one HashMap operation.

Exact Word Search

The search method validates both path existence and word completion. It returns true only if the query terminates at a node where last is true.

public boolean search(String word) {
    TrieNode current = root;
    for (char c : word.toCharArray()) {
        if (!current.map.containsKey(c)) return false;
        current = current.map.get(c);
    }
    return current.last; // true only if a full word ends here
}

Prefix Validation for Autocomplete

The startsWith method, essential for autocomplete functionality, verifies that a prefix path exists without requiring a complete word boundary.

public boolean startsWith(String prefix) {
    TrieNode current = root;
    for (char c : prefix.toCharArray()) {
        if (!current.map.containsKey(c)) return false;
        current = current.map.get(c);
    }
    return true; // path exists → at least one word shares the prefix
}

To generate actual suggestion lists, perform a depth-first search (DFS) from the node returned by the prefix traversal, collecting all descendant nodes where last is true.

Supporting Wildcard Patterns

The repository extends the basic Trie to support regular-expression-like wildcards in leetcode/trie/AddAndSearchWordDataStructureDesign.java (lines 20-65). This implementation uses a fixed-size array instead of a HashMap for constant-time index-based access.

Node Structure Differences

Unlike the HashMap version, this variant stores children in a TrieNode[26] array indexed by character - 'a', and uses a String item field (non-empty indicates word completion) rather than a boolean flag.

Recursive Wildcard Matching

The . character matches any single letter. The algorithm recursively explores all non-null children when encountering a wildcard.

public boolean search(String word) {
    return match(word.toCharArray(), 0, root);
}

private boolean match(char[] chs, int k, TrieNode node) {
    if (k == chs.length) return node.item != "";
    if (chs[k] != '.') {
        return node.children[chs[k] - 'a'] != null &&
               match(chs, k + 1, node.children[chs[k] - 'a']);
    }
    for (TrieNode child : node.children) {
        if (child != null && match(chs, k + 1, child)) return true;
    }
    return false;
}

This implementation favors array indexing speed over space efficiency, making it ideal for dense alphabets like lowercase English letters.

Practical Usage Examples

Basic Autocomplete Implementation

public class AutoCompleteDemo {
    public static void main(String[] args) {
        ImplementTrie trie = new ImplementTrie();
        
        trie.insert("apple");
        trie.insert("app");
        trie.insert("application");
        trie.insert("banana");
        
        System.out.println(trie.search("app"));      // true
        System.out.println(trie.startsWith("ban"));  // true
        System.out.println(trie.startsWith("cat"));  // false
    }
}

Wildcard Pattern Matching

public class WildcardDemo {
    public static void main(String[] args) {
        AddAndSearchWordDataStructure ds = new AddAndSearchWordDataStructure();
        
        ds.addWord("bad");
        ds.addWord("dad");
        ds.addWord("mad");
        
        System.out.println(ds.search("pad"));   // false
        System.out.println(ds.search("bad"));   // true
        System.out.println(ds.search(".ad"));   // true (matches bad, dad, mad)
        System.out.println(ds.search("b.."));   // true (matches bad)
    }
}

Design Trade-offs and Performance

Choosing between the two implementations depends on your specific constraints:

• HashMap approach (ImplementTrie.java): Optimal for sparse character distributions or large alphabets (e.g., Unicode), as it allocates space only for existing edges.
• Fixed array approach (AddAndSearchWordDataStructureDesign.java): Delivers constant-time child access with lower constant factors for dense, limited alphabets (e.g., a-z).

Both variants guarantee O(L) time complexity for insert and search operations, where L is the string length. Memory efficiency stems from prefix sharing—common prefixes like "app" in "apple" and "application" share the same initial nodes, reducing redundancy compared to flat storage structures.

Summary

• A TrieNode requires a child map (HashMap or array), a character value, and a completion marker to form the tree structure.
• The HashMap implementation in leetcode/trie/ImplementTrie.java provides dynamic child management suitable for general-purpose autocomplete systems.
• Fixed-size arrays in the wildcard variant enable O(1) indexing and support pattern matching with the . wildcard character.
• All core operations—insert, search, and startsWith—execute in O(L) time, scaling efficiently regardless of total stored word volume.

Frequently Asked Questions

What is the time complexity of Trie operations?

All fundamental operations—insertion, exact search, and prefix validation—run in O(L) time, where L is the length of the input string. This efficiency holds because the algorithm traverses exactly one path down the tree, performing constant-time work per character.

How does a Trie save memory compared to a hash table?

A Trie achieves prefix compression by sharing common initial segments of words. For example, storing "car", "card", and "care" requires only five nodes total (c-a-r-d-e), whereas a hash table stores three complete string objects independently. This advantage increases with larger datasets containing many shared prefixes.

When should I use a HashMap versus an array for Trie nodes?

Use a HashMap when the alphabet size is large or sparse (e.g., supporting all Unicode characters), as it allocates memory only for existing edges. Use a fixed-size array (typically size 26 for lowercase English) when the alphabet is small and dense, as it provides faster constant-time access without hashing overhead.

How do I retrieve all autocomplete suggestions from a Trie?

First, traverse the prefix using the startsWith logic to locate the terminal node of the prefix. Then, perform a depth-first search (DFS) or breadth-first search (BFS) from that node, collecting the strings built from paths that terminate at nodes marked as complete words (where last is true or item is non-empty).

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}