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

> Implement a Trie prefix tree for efficient string searching and autocomplete in O(L) time. Learn how this data structure overcomes common limitations.

- Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews)
- Tags: how-to-guide
- Published: 2026-03-04

---

**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`](https://github.com/kdn251/interviews/blob/main/ImplementTrie.java)

The foundation of the data structure rests on two primary classes defined in [`leetcode/trie/ImplementTrie.java`](https://github.com/kdn251/interviews/blob/main/leetcode/trie/ImplementTrie.java): the node container and the public API manager.

### The TrieNode Structure

According to lines 11-16 of [`ImplementTrie.java`](https://github.com/kdn251/interviews/blob/main/ImplementTrie.java), each node maintains a **HashMap** for child edges, a character value, and a completion flag.

```java
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`.

```java
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`.

```java
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.

```java
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`](https://github.com/kdn251/interviews/blob/main/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.

```java
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

```java
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

```java
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`](https://github.com/kdn251/interviews/blob/main/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`](https://github.com/kdn251/interviews/blob/main/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`](https://github.com/kdn251/interviews/blob/main/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).