Trie Data Structure: Complete Guide with Code Examples

A trie (pronounced "try", from retrieval) is a tree-like data structure optimised for storing and searching strings by their prefixes. Instead of hashing an entire key, a trie decomposes each key into its characters and stores them along branches — every path from root to a marked node spells out a word.

Tries power autocomplete, spell-checkers, IP routing tables, and competitive-programming prefix problems. They trade memory for lightning-fast prefix queries.

Quick reference

What is a trie?

Each node in a trie represents one character. Children of a node are the characters that can follow it. A special end-of-word flag on a node marks where a complete word finishes.

Words: ["cat", "car", "card", "care", "dog"]

          root
         /    \
        c      d
        |      |
        a      o
       / \     |
      t   r    g*
      *  / \
        d   e
        *   *

Nodes marked with * = is_end = True.

Notice how "car", "card", and "care" share the path c → a → r, only diverging at the last character. This prefix sharing is why tries excel at autocomplete.

Core operations

Insert

Walk the trie character by character. Create a new node wherever a character is missing. Set is_end = True on the final node.

Insert "care" into a trie containing "car":

c → a → r → e   (create node 'e', set is_end)
         *       ('r' node already has is_end from "car")

Search

Walk the trie. If any character is missing → word not found. If you reach the end but is_end is False → prefix exists but not the whole word.

Starts-with

Same as search, but don't check is_end at the end — just confirm the path exists.

Implementations

Python

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False
        self.count = 0  # words passing through this node


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.count += 1
        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 count_words_with_prefix(self, prefix: str) -> int:
        node = self._find(prefix)
        return node.count if node else 0

    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

    def delete(self, word: str) -> bool:
        """Returns True if word was deleted."""
        def _delete(node: TrieNode, word: str, depth: int) -> bool:
            if depth == len(word):
                if not node.is_end:
                    return False
                node.is_end = False
                return len(node.children) == 0  # safe to delete this node

            ch = word[depth]
            if ch not in node.children:
                return False

            child = node.children[ch]
            should_delete = _delete(child, 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)

    def list_all_words(self) -> list[str]:
        results = []
        def dfs(node: TrieNode, path: list[str]):
            if node.is_end:
                results.append("".join(path))
            for ch, child in node.children.items():
                path.append(ch)
                dfs(child, path)
                path.pop()
        dfs(self.root, [])
        return results


# Usage
trie = Trie()
for word in ["apple", "app", "apply", "apt", "bat"]:
    trie.insert(word)

print(trie.search("app"))          # True
print(trie.search("ap"))           # False
print(trie.starts_with("ap"))      # True
print(trie.count_words_with_prefix("app"))  # 3
print(trie.list_all_words())       # ['app', 'apple', 'apply', 'apt', 'bat']
trie.delete("apple")
print(trie.search("apple"))        # False
print(trie.search("app"))          # True (still there)

JavaScript

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;
  }

  // Return all words starting with prefix
  autocomplete(prefix) {
    const node = this._find(prefix);
    if (!node) return [];

    const results = [];
    const dfs = (n, path) => {
      if (n.isEnd) results.push(prefix + path);
      for (const [ch, child] of n.children) {
        dfs(child, path + ch);
      }
    };
    dfs(node, "");
    return results;
  }
}

// Usage
const trie = new Trie();
["apple", "app", "apply", "apt", "bat"].forEach(w => trie.insert(w));

console.log(trie.search("app"));       // true
console.log(trie.startsWith("ap"));    // true
console.log(trie.autocomplete("app")); // ["app", "apple", "apply"]

Java

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}

public class Trie {
    private final TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

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

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

    private TrieNode find(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            if (!node.children.containsKey(ch)) return null;
            node = node.children.get(ch);
        }
        return node;
    }

    public List<String> autocomplete(String prefix) {
        List<String> results = new ArrayList<>();
        TrieNode node = find(prefix);
        if (node == null) return results;
        dfs(node, new StringBuilder(prefix), results);
        return results;
    }

    private void dfs(TrieNode node, StringBuilder path, List<String> results) {
        if (node.isEnd) results.add(path.toString());
        for (Map.Entry<Character, TrieNode> e : node.children.entrySet()) {
            path.append(e.getKey());
            dfs(e.getValue(), path, results);
            path.deleteCharAt(path.length() - 1);
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        for (String w : new String[]{"apple", "app", "apply", "apt", "bat"}) {
            trie.insert(w);
        }
        System.out.println(trie.search("app"));          // true
        System.out.println(trie.startsWith("ap"));       // true
        System.out.println(trie.autocomplete("app"));    // [app, apple, apply]
    }
}

Go

package main

import "fmt"

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd    bool
}

func newTrieNode() *TrieNode {
    return &TrieNode{children: make(map[rune]*TrieNode)}
}

type Trie struct {
    root *TrieNode
}

func NewTrie() *Trie { return &Trie{root: newTrieNode()} }

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if _, ok := node.children[ch]; !ok {
            node.children[ch] = newTrieNode()
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (t *Trie) find(prefix string) *TrieNode {
    node := t.root
    for _, ch := range prefix {
        if _, ok := node.children[ch]; !ok {
            return nil
        }
        node = node.children[ch]
    }
    return node
}

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

func (t *Trie) StartsWith(prefix string) bool {
    return t.find(prefix) != nil
}

func (t *Trie) Autocomplete(prefix string) []string {
    node := t.find(prefix)
    if node == nil {
        return nil
    }
    var results []string
    var dfs func(*TrieNode, []rune)
    dfs = func(n *TrieNode, path []rune) {
        if n.isEnd {
            results = append(results, prefix+string(path))
        }
        for ch, child := range n.children {
            dfs(child, append(path, ch))
        }
    }
    dfs(node, nil)
    return results
}

func main() {
    t := NewTrie()
    for _, w := range []string{"apple", "app", "apply", "apt", "bat"} {
        t.Insert(w)
    }
    fmt.Println(t.Search("app"))         // true
    fmt.Println(t.StartsWith("ap"))      // true
    fmt.Println(t.Autocomplete("app"))   // [app apple apply]
}

Classic interview problems

1. Implement Trie (LeetCode 208) — Easy

The standard implementation above covers this exactly: insert, search, startsWith.

Key point: search must check is_end; startsWith must not.

2. Word Search II (LeetCode 212) — Hard

Find all words from a dictionary that exist in an m×n board (DFS).

def find_words(board: list[list[str]], words: list[str]) -> list[str]:
    trie = Trie()
    for w in words:
        trie.insert(w)

    rows, cols = len(board), len(board[0])
    found = set()

    def dfs(node, r, c, path):
        ch = board[r][c]
        if ch not in node.children:
            return
        next_node = node.children[ch]
        path.append(ch)
        if next_node.is_end:
            found.add("".join(path))
        board[r][c] = "#"  # mark visited
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                dfs(next_node, nr, nc, path)
        board[r][c] = ch   # restore
        path.pop()

    for r in range(rows):
        for c in range(cols):
            dfs(trie.root, r, c, [])

    return list(found)

Why trie? Pruning — if no word starts with the current path, stop immediately. O(M × 4 × 3^(L−1)) vs O(M × W × L) brute-force.

3. Replace Words (LeetCode 648) — Medium

Replace every word in a sentence with its shortest dictionary root.

def replace_words(dictionary: list[str], sentence: str) -> str:
    trie = Trie()
    for root in dictionary:
        trie.insert(root)

    def find_root(word):
        node = trie.root
        for i, ch in enumerate(word):
            if ch not in node.children:
                break
            node = node.children[ch]
            if node.is_end:
                return word[:i+1]  # shortest root found
        return word

    return " ".join(find_root(w) for w in sentence.split())

# replace_words(["cat","bat","rat"], "the cattle was rattled by the battery")
# → "the cat was rat by the bat"

4. Design Search Autocomplete System (LeetCode 642) — Hard

Return top-3 hot sentences that start with the typed prefix, ranked by frequency then lexicographically.

import heapq
from collections import defaultdict

class AutocompleteSystem:
    def __init__(self, sentences: list[str], times: list[int]):
        self.freq = defaultdict(int)
        for s, t in zip(sentences, times):
            self.freq[s] = t
        self.trie = Trie()
        for s in sentences:
            self.trie.insert(s)
        self.current = []

    def input(self, c: str) -> list[str]:
        if c == "#":
            sentence = "".join(self.current)
            self.freq[sentence] += 1
            self.trie.insert(sentence)
            self.current = []
            return []

        self.current.append(c)
        prefix = "".join(self.current)
        candidates = self.trie.list_words_with_prefix(prefix)
        # Top 3: highest frequency, break ties lexicographically
        return heapq.nlargest(3, candidates, key=lambda s: (self.freq[s], [-ord(x) for x in s]))

5. Longest Word in Dictionary (LeetCode 720) — Medium

Find the longest word buildable one character at a time, where every prefix is also in the dictionary.

def longest_word(words: list[str]) -> str:
    trie = Trie()
    for w in words:
        trie.insert(w)

    best = ""
    def dfs(node, path):
        nonlocal best
        word = "".join(path)
        if len(word) > len(best) or (len(word) == len(best) and word < best):
            best = word
        for ch, child in node.children.items():
            if child.is_end:  # every prefix must be a valid word
                path.append(ch)
                dfs(child, path)
                path.pop()

    dfs(trie.root, [])
    return best

# longest_word(["w","wo","wor","worl","world"]) → "world"

6. Palindrome Pairs (LeetCode 336) — Hard

Find all pairs (i, j) where words[i] + words[j] is a palindrome.

A trie of reversed words enables checking: for each word, look for reversed suffixes that are palindromes.

Concept: insert all reversed(word) into trie. For each word, traverse the trie — if remaining trie path forms a palindrome (or remaining word suffix is a palindrome), it's a valid pair.

Trie variants

Trie vs hash table vs sorted array

Rule of thumb: reach for a trie when you need prefix queries or autocomplete; reach for a hash table when you only need exact lookups.

When to use a trie

Use a trie when:

• You need prefix search (autocomplete, IP routing, spell-check).
• Multiple strings share long common prefixes (saves memory vs storing each separately).
• You need lexicographic ordering without sorting.
• The problem involves building words character by character.
• You need to prune a search space by prefix (Word Search II, Boggle).

Do NOT use a trie when:

• You only need exact match lookups — a hash set is simpler and faster in practice.
• The alphabet is huge (Unicode with no bound) — each node may have thousands of children; a hash map per node mitigates this but adds overhead.
• Memory is critical — a trie with 26-child arrays uses ~26 × 8 bytes per node even when mostly empty.
• The strings are numbers or binary data — consider a bitwise trie or segment tree instead.

Memory optimisation

Array-based children (fast, memory-hungry):

class TrieNode:
    def __init__(self):
        self.children = [None] * 26  # only lowercase a-z
        self.is_end = False

# Access: node.children[ord(ch) - ord('a')]
# Memory: 26 pointers × 8 bytes = 208 bytes/node (even when sparse)

Dict-based children (flexible, slightly slower):

class TrieNode:
    def __init__(self):
        self.children: dict[str, TrieNode] = {}
        self.is_end = False
# Memory: only stores existing children — better for large alphabets or sparse tries

Compressed trie (merge single-child chains):

Instead of: r → u → n → n → i → n → g*
Store:       r → "unnin" → g*   (one edge = multi-char string)

Reduces node count from O(N × L) to O(N) for N words.

Complexity summary

Common mistakes

Trie vs related structures

FAQ

Q: Is "trie" pronounced "tree" or "try"? Officially "try" (from retrieval), but "tree" is widely heard. Both are understood.

Q: Trie vs hash set for interview problems — which to use? If the problem involves prefixes, autocomplete, or character-by-character building → trie. If only exact lookups → hash set is simpler.

Q: How does a trie handle Unicode? Use a dict (or HashMap) per node keyed on the full Unicode character. Array-based children only work for fixed, small alphabets.

Q: What's the difference between a trie and a prefix tree? They're the same thing. "Prefix tree" is the descriptive name; "trie" is the historical name from "retrieval".

Q: Can a trie store integers? Yes — a bitwise trie treats each bit of an integer as a 0/1 branch. Used for XOR maximisation problems and radix-based sorting.

Q: What is Aho-Corasick and how does it relate to tries? Aho-Corasick extends a trie with failure links (similar to KMP), enabling simultaneous search for multiple patterns in O(N + M + Z) where Z is match count. Standard tries search one pattern at a time.