Trie (Prefix Tree): Complete Reference

TL;DR

• Bottom line: A trie provides O(m) insert, search, and prefix-lookup for strings of length m, independent of the total number of stored keys.
• Key tool/command: children = {} (hash-map node) or children = [None]*26 (fixed-array node) at each trie level.
• Watch out for: Memory explosion with large alphabets -- use hash-map children instead of fixed-size arrays for anything beyond lowercase a-z.
• Works with: Any programming language; no external dependencies. Standard CS data structure since Fredkin (1960).

Constraints

• Memory usage grows with alphabet size: each node may hold up to |Σ| child pointers (26 for lowercase, 128 for ASCII, 1M+ for Unicode).
• Tries are not cache-friendly due to pointer chasing; for latency-critical paths, consider array-based or DAFSA alternatives.
• Delete operations must not orphan subtrees: always check whether a node still has children before removing it.
• For Unicode strings, use hash-map children (not fixed arrays) to avoid allocating millions of slots per node.
• Trie depth equals the length of the longest key; extremely long keys create deep, thin trees -- consider compressed tries (radix trees) to collapse single-child chains.

Quick Reference

Decision Tree

START
|-- Need prefix-based operations (autocomplete, startsWith, longest prefix)?
|   |-- YES --> Use a Trie (this unit)
|   +-- NO |
|-- Need only exact-match lookup?
|   |-- YES --> Use a HashMap / HashSet (O(1) average)
|   +-- NO |
|-- Need sorted iteration of keys?
|   |-- YES --> Use a sorted array + binary search, or balanced BST
|   +-- NO |
|-- Keys are integers and you need XOR-max queries?
|   |-- YES --> Use a binary trie (bitwise trie)
|   +-- NO |
|-- Memory is severely constrained and keys share few prefixes?
|   |-- YES --> Use a HashMap; tries waste memory on sparse trees
|   +-- NO |
+-- DEFAULT --> Trie with hash-map children is a safe general choice

Step-by-Step Guide

1. Implement the TrieNode class

Each node holds a mapping from character to child node and a boolean flag indicating end-of-word. [src1]

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False  # marks complete word

Verify: node = TrieNode(); assert node.children == {} and node.is_end == False

2. Implement insert

Walk the trie character by character, creating nodes as needed, and mark the final node. [src1]

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

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

Verify: t = Trie(); t.insert("apple"); assert "a" in t.root.children

3. Implement search and starts_with

Search requires is_end == True at the final node; starts_with only requires the path exists. [src4]

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

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

def _find_node(self, prefix: str):
    node = self.root
    for ch in prefix:
        if ch not in node.children:
            return None
        node = node.children[ch]
    return node

Verify: t.insert("apple"); assert t.search("apple") and not t.search("app") and t.starts_with("app")

4. Implement delete

Bottom-up recursive removal: only delete nodes that are not shared with other words. [src5]

def delete(self, word: str) -> bool:
    def _delete(node, word, depth):
        if depth == len(word):
            if not node.is_end:
                return False
            node.is_end = False
            return len(node.children) == 0
        ch = word[depth]
        if ch not in node.children:
            return False
        should_delete = _delete(node.children[ch], word, depth + 1)
        if should_delete:
            del node.children[ch]
            return not node.is_end and len(node.children) == 0
        return False
    return _delete(self.root, word, 0)

Verify: t.insert("apple"); t.insert("app"); t.delete("apple"); assert t.search("app") and not t.search("apple")

5. Add autocomplete

Collect all words under a given prefix using DFS. [src3]

def autocomplete(self, prefix: str, limit: int = 10) -> list:
    node = self._find_node(prefix)
    if node is None:
        return []
    results = []
    def dfs(node, path):
        if len(results) >= limit:
            return
        if node.is_end:
            results.append(prefix + path)
        for ch in sorted(node.children):
            dfs(node.children[ch], path + ch)
    dfs(node, "")
    return results

Verify: t.insert("app"); t.insert("apple"); t.insert("application"); assert t.autocomplete("app") == ["app", "apple", "application"]

Code Examples

Python: Full Trie with all operations

# Input:  list of words to insert, queries to search/autocomplete
# Output: boolean search results, list of autocomplete suggestions

class TrieNode:
    __slots__ = ('children', 'is_end')  # memory optimization
    def __init__(self):
        self.children = {}
        self.is_end = False

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

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

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end

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

    def _find(self, prefix: str):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

JavaScript: Trie with autocomplete

// Input:  words array, prefix string
// Output: array of autocomplete suggestions

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  constructor() { this.root = new TrieNode(); }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch))
        node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isEnd = true;
  }

  search(word) {
    const node = this.#find(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix) {
    return this.#find(prefix) !== null;
  }

  #find(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }
}

Java: Trie with array-based children (lowercase a-z)

// Input:  String words, String prefix
// Output: boolean for search, List for autocomplete

class Trie {
    private static final int ALPHA = 26;
    private int[][] children;
    private boolean[] isEnd;
    private int size = 0;

    public Trie(int maxNodes) {
        children = new int[maxNodes][ALPHA];
        isEnd = new boolean[maxNodes];
        for (int[] row : children) Arrays.fill(row, -1);
        size = 1;  // root = node 0
    }

    public void insert(String word) {
        int node = 0;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (children[node][idx] == -1)
                children[node][idx] = size++;
            node = children[node][idx];
        }
        isEnd[node] = true;
    }

    public boolean search(String word) {
        int node = find(word);
        return node != -1 && isEnd[node];
    }

    private int find(String s) {
        int node = 0;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (children[node][idx] == -1) return -1;
            node = children[node][idx];
        }
        return node;
    }
}

Go: Trie with map children

// Input:  strings to insert, prefix to search
// Output: bool for search, []string for autocomplete

package trie

type TrieNode struct {
    Children map[byte]*TrieNode
    IsEnd    bool
}

type Trie struct { Root *TrieNode }

func NewTrie() *Trie {
    return &Trie{Root: &TrieNode{
        Children: make(map[byte]*TrieNode),
    }}
}

func (t *Trie) Insert(word string) {
    node := t.Root
    for i := 0; i < len(word); i++ {
        ch := word[i]
        if _, ok := node.Children[ch]; !ok {
            node.Children[ch] = &TrieNode{
                Children: make(map[byte]*TrieNode),
            }
        }
        node = node.Children[ch]
    }
    node.IsEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.find(word)
    return node != nil && node.IsEnd
}

func (t *Trie) find(prefix string) *TrieNode {
    node := t.Root
    for i := 0; i < len(prefix); i++ {
        child, ok := node.Children[prefix[i]]
        if !ok { return nil }
        node = child
    }
    return node
}

Anti-Patterns

Wrong: Using fixed array[26] for variable alphabets

# BAD -- allocates 26 slots per node even when alphabet is larger
class TrieNode:
    def __init__(self):
        self.children = [None] * 26  # breaks for uppercase, digits, Unicode
        self.is_end = False

    def insert_char(self, c):
        idx = ord(c) - ord('a')  # IndexError for 'A', '0', etc.

Correct: Use a dictionary for flexible alphabets

# GOOD -- handles any character set, allocates only for characters present
class TrieNode:
    def __init__(self):
        self.children = {}  # works with any hashable character
        self.is_end = False

Wrong: Delete without checking children

# BAD -- naively sets is_end to False without cleanup
def bad_delete(self, word):
    node = self.root
    for ch in word:
        node = node.children[ch]
    node.is_end = False  # leaves orphaned nodes in memory

Correct: Bottom-up delete with child check

# GOOD -- only removes nodes that have no children and are not end-of-word
def delete(self, word):
    def _del(node, word, d):
        if d == len(word):
            if not node.is_end: return False
            node.is_end = False
            return len(node.children) == 0
        ch = word[d]
        if ch not in node.children: return False
        should_del = _del(node.children[ch], word, d + 1)
        if should_del:
            del node.children[ch]
            return not node.is_end and len(node.children) == 0
        return False
    _del(self.root, word, 0)

Wrong: Not using __slots__ in Python

# BAD -- each TrieNode carries a full __dict__, wasting ~100+ bytes per node
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

Correct: Use __slots__ to reduce per-node memory

# GOOD -- __slots__ eliminates __dict__, saving ~60-100 bytes per node
class TrieNode:
    __slots__ = ('children', 'is_end')
    def __init__(self):
        self.children = {}
        self.is_end = False

Common Pitfalls

• Memory blowup on large alphabets: A trie with 1M words of average length 10 using [None]*128 (ASCII) allocates ~1.28 billion slots. Fix: use dict or Map children. [src6]
• Forgetting is_end flag: Inserting "apple" makes "app" traversable but not findable without the end marker. Fix: always check is_end in search(). [src1]
• Not compressing single-child chains: A trie storing URLs creates one node per character in the shared prefix. Fix: use a radix tree (compressed trie) to merge single-child chains into edge labels. [src2]
• Wildcard search without result limit: Patterns like ... (all wildcards) degenerate to full-tree DFS. Fix: impose a maximum result count or depth limit. [src4]
• Thread safety with concurrent inserts: Tries are not inherently thread-safe. Fix: use a read-write lock or concurrent trie (Ctrie). [src7]
• Case sensitivity mismatch: Inserting "Apple" but searching "apple" fails. Fix: normalize keys to lowercase before insert and search. [src3]

When to Use / When Not to Use

Important Caveats

• Tries invented by Fredkin (1960) are a foundational data structure; the concept is stable and not subject to breaking changes. The term "trie" comes from retrieval, not "tree."
• In practice, hash maps often outperform tries for exact lookups due to better cache locality, even though tries have better worst-case guarantees (O(m) vs O(m) average for hash, O(m×n) worst).
• Compressed variants (radix trees, Patricia tries, DAFSA) significantly reduce memory usage but add implementation complexity. Libraries like datrie (Python), art (Go), or apache/commons-collections (Java) provide production-ready implementations.
• For competitive programming, array-based tries with pre-allocated nodes are preferred for speed; for production code, hash-map-based tries are preferred for flexibility.