Trie (Prefix Tree)

A Trie (derived from retrieval, pronounced "try") is a tree-like data structure used for storing and searching strings efficiently. It is widely used in autocomplete engines, spell checkers, and IP routing tables.

Unlike a binary search tree, no node in the tree stores the key associated with that node. Instead, its position in the tree defines which key it is associated with. All descendants of a node share a common prefix.

       (root)
      /   |   \
     a    c    t
    /     |     \
   p      a      o
  /       |       \
 p        t        p (end)
/
l
|
e (end)

Complexity Analysis

Operation	Time Complexity	Space Complexity
Insert	O(L)	O(L · Σ) worst case
Search	O(L)	O(1)
StartsWith (Prefix)	O(L)	O(1)

Where:

• L is the length of the word/query.
• Σ is the alphabet size (e.g., 26 for lowercase English letters, 256 for ASCII).

Implementation (Python)

Using a hash map for child nodes provides optimal memory usage while maintaining O(1) child lookups.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

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

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

    def search(self, word: str) -> bool:
        curr = self._find_node(word)
        return curr is not None and curr.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None

    def _find_node(self, prefix: str) -> TrieNode | None:
        curr = self.root
        for char in prefix:
            if char not in curr.children:
                return None
            curr = curr.children[char]
        return curr

Implementation (Java)

Using a fixed-size array (char - 'a') is cache-efficient when the character set is restricted to lowercase English alphabet:

public class Trie {
    private static class TrieNode {
        private final TrieNode[] children = new TrieNode[26];
        private boolean isEndOfWord = false;
    }

    private final TrieNode root;

    public Trie() {
        this.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.isEndOfWord = true;
    }

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

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

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

Common Use Cases

1. Autocomplete & Predictive Text: Finding all words matching a given prefix by traversing down to the prefix node and collecting all subtree words (via DFS/BFS).
2. Spell Checking: Quickly verifying if a word exists in a dictionary.
3. Longest Prefix Matching: Used in network routers to match IP addresses against routing tables.
4. Radix Tree / Compressed Trie: Optimizes space by merging consecutive single-child nodes into single edges (used in Git trees and Linux kernel page tables).