Quick Reference O(m) per operation / O(m) per word

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}
class Trie {
    TrieNode root = new TrieNode();
    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;
    }
    boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) return false;
            node = node.children.get(ch);
        }
        return node.isEnd;
    }
}

type TrieNode struct {
    children map[byte]*TrieNode
    isEnd    bool
}
type Trie struct { root *TrieNode }

func (t *Trie) Insert(word string) {
    node := t.root
    for i := range word {
        ch := word[i]
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{children: map[byte]*TrieNode{}}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}
func (t *Trie) Search(word string) bool {
    node := t.root
    for i := range word {
        if node.children[word[i]] == nil { return false }
        node = node.children[word[i]]
    }
    return node.isEnd
}

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

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

    def insert(self, word):
        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):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

use std::collections::HashMap;
struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_end: bool,
}
struct Trie { root: TrieNode }
impl Trie {
    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for ch in word.chars() {
            node = node.children.entry(ch).or_insert(
                TrieNode { children: HashMap::new(), is_end: false });
        }
        node.is_end = true;
    }
    fn search(&self, word: &str) -> bool {
        let mut node = &self.root;
        for ch in word.chars() {
            match node.children.get(&ch) {
                Some(n) => node = n,
                None => return false,
            }
        }
        node.is_end
    }
}

class TrieNode {
    children = new Map<string, TrieNode>();
    isEnd = false;
}
class Trie {
    root = new TrieNode();
    insert(word: string): void {
        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: string): boolean {
        let node = this.root;
        for (const ch of word) {
            if (!node.children.has(ch)) return false;
            node = node.children.get(ch)!;
        }
        return node.isEnd;
    }
}

Use when

Prefix-based search
Autocomplete / word dictionary
Word search in grid
Longest common prefix

Watch out

Not marking end of word
Not handling deletion properly
Using trie when hash set suffices (no prefix queries needed)

Pattern

Trie (Prefix Tree)

Store and search strings efficiently using a tree that shares common prefixes between words.

Roadmap

What Is This Pattern?
When to Use It
Variant 1 — Basic Trie (Insert / Search / StartsWith)
Variant 2 — Trie with Wildcards or Counting
Template Code
Visual Walkthrough
Common Problems
Interactive Demo
Complexity Analysis
Key Takeaways

Step 01

What Is This Pattern?

A trie (pronounced "try") is a tree-shaped data structure where every node represents a single character. Strings that share a common prefix share the same path from the root. This means inserting, searching, and prefix-matching all take O(L) time, where L is the length of the word — completely independent of how many words are stored.

The Core Idea

Each edge represents a character. A path from root to a marked node spells out a word. Shared prefixes are stored only once.

root

          Words stored: "app", "apple", "top" — * = end of word
        

💡

Why not just use a hash set? A hash set can check if a word exists, but it cannot efficiently answer "what words start with this prefix?" A trie answers prefix queries in O(prefix length) and naturally supports autocomplete, spell-check, and wildcard matching — all operations that hash-based structures struggle with.

Step 02

When to Use It

Look for these recognition signals in the problem statement. If you spot one, a trie is very likely the intended data structure.

"Prefix matching" or "startsWith"

Check if any stored word begins with a given prefix. This is the classic trie operation.

"Autocomplete" or "search suggestions"

Given a prefix, return all words that start with it. Trie traversal collects them naturally.

"Word dictionary" with "wildcards"

Search for words where some characters are unknown (like '.'). DFS on a trie handles wildcard branches.

"Replace words" or "shortest prefix"

Find the shortest prefix of a word that exists in a dictionary. Walk the trie and stop at the first end-of-word marker.

⚡

The key clue: You need to store a dictionary of strings and perform prefix-based operations (prefix search, prefix replacement, or character-by-character matching). A brute-force approach checking every word is O(N * L). A trie reduces prefix lookups to O(L) regardless of dictionary size.

Step 03

Variant 1 — Basic Trie (Insert / Search / StartsWith)

Core Operations

The basic trie supports three operations: insert a word, search for an exact word, and check if any word starts with a given prefix. Each node has up to 26 children (for lowercase English letters) and an isEnd flag.

Walkthrough: insert("cat"), insert("car"), search("cat"), startsWith("ca")

Building a trie step by step, then querying it.

insert("cat")

Start at root. Create child c, then a, then t. Mark t as end-of-word.

→

insert("car")

Start at root. c already exists, a already exists. Create new child r. Mark it as end-of-word. The prefix "ca" is shared.

→

search("cat")

Traverse root → c → a → t. Node t has isEnd = true. Return true.

✓

startsWith("ca")

Traverse root → c → a. Node exists (regardless of isEnd). Return true.

✓

Step 04

Variant 2 — Trie with Wildcards or Counting

Advanced Operations

Extend the basic trie with two powerful capabilities: wildcard search (matching '.' against any character) and prefix counting (tracking how many words pass through or end at each node).

Wildcard Search: search("c.t")

When we encounter a '.', we branch out to all children using DFS. If any branch leads to a match, return true.

          char 'c': Exact match. Move to child 'c'.
        
          char '.': Wildcard! Try every child of 'c'. We have 'a' → continue DFS for each.
        
          char 't': In the 'a' branch: child 't' exists and isEnd = true. Match found!

Counting Variant: passCount & endCount

Each node stores two counters: passCount (how many words pass through this node) and endCount (how many words end here). This enables "count words with prefix" and "count exact matches."

          insert("app"): root(pass:1) → a(pass:1) → p(pass:1) → p(pass:1, end:1)
        
          insert("apple"): root(pass:2) → a(pass:2) → p(pass:2) → p(pass:2, end:1) → l(pass:1) → e(pass:1, end:1)
        
          countPrefix("app"): Walk to node 'p' (second p). passCount = 2 (both "app" and "apple" pass through).
        
          countWord("app"): Walk to node 'p' (second p). endCount = 1 (only "app" ends here).

🎯

Choosing the variant: Use the basic trie when you only need insert, search, and startsWith. Add wildcard DFS for pattern matching with unknown characters. Add counting fields when you need to know how many words share a prefix (e.g., Map Sum Pairs) or support deletion.

Step 05

Template Code

Here is the annotated Java template for a standard trie with insert, search, and startsWith.

Trie Node + Core Operations

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null)
                node.children[idx] = new TrieNode();  // create if missing
            node = node.children[idx];                // move down
        }
        node.isEnd = true;                          // mark end of word
    }

    boolean search(String word) {
        TrieNode node = traverse(word);
        return node != null && node.isEnd;          // must be end-of-word
    }

    boolean startsWith(String prefix) {
        return traverse(prefix) != null;            // just needs to exist
    }

    // Helper: walk down the trie following each char
    TrieNode traverse(String s) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return null;
            node = node.children[idx];
        }
        return node;
    }
}

type TrieNode struct {
    children [26]*TrieNode
    isEnd    bool
}

type Trie struct {
    root *TrieNode
}

func Constructor() Trie {
    return Trie{root: &TrieNode{}}
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        idx := ch - 'a'
        if node.children[idx] == nil {
            node.children[idx] = &TrieNode{}  // create if missing
        }
        node = node.children[idx]               // move down
    }
    node.isEnd = true                           // mark end of word
}

func (t *Trie) Search(word string) bool {
    node := t.traverse(word)
    return node != nil && node.isEnd            // must be end-of-word
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.traverse(prefix) != nil           // just needs to exist
}

// Helper: walk down the trie following each char
func (t *Trie) traverse(s string) *TrieNode {
    node := t.root
    for _, ch := range s {
        idx := ch - 'a'
        if node.children[idx] == nil {
            return nil
        }
        node = node.children[idx]
    }
    return node
}

class TrieNode:
    def __init__(self):
        self.children: list[TrieNode | None] = [None] * 26
        self.is_end: bool = False

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

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = TrieNode()  # create if missing
            node = node.children[idx]              # move down
        node.is_end = True                        # mark end of word

    def search(self, word: str) -> bool:
        node = self._traverse(word)
        return node is not None and node.is_end  # must be end-of-word

    def starts_with(self, prefix: str) -> bool:
        return self._traverse(prefix) is not None # just needs to exist

    # Helper: walk down the trie following each char
    def _traverse(self, s: str) -> TrieNode | None:
        node = self.root
        for c in s:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                return None
            node = node.children[idx]
        return node

struct TrieNode {
    children: [Option<Box<TrieNode>>; 26],
    is_end: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: std::array::from_fn(|_| None),
            is_end: false,
        }
    }
}

struct Trie {
    root: TrieNode,
}

impl Trie {
    pub fn new() -> Self {
        Trie { root: TrieNode::new() }
    }

    pub fn insert(&mut self, word: String) {
        let mut node = &mut self.root;
        for ch in word.bytes() {
            let idx = (ch - b'a') as usize;
            if node.children[idx].is_none() {
                node.children[idx] = Some(Box::new(TrieNode::new()));  // create if missing
            }
            node = node.children[idx].as_mut().unwrap();               // move down
        }
        node.is_end = true;                                              // mark end of word
    }

    pub fn search(&self, word: String) -> bool {
        match self.traverse(&word) {
            Some(node) => node.is_end,   // must be end-of-word
            None => false,
        }
    }

    pub fn starts_with(&self, prefix: String) -> bool {
        self.traverse(&prefix).is_some()  // just needs to exist
    }

    // Helper: walk down the trie following each char
    fn traverse(&self, s: &str) -> Option<&TrieNode> {
        let mut node = &self.root;
        for ch in s.bytes() {
            let idx = (ch - b'a') as usize;
            match &node.children[idx] {
                None => return None,
                Some(child) => node = child,
            }
        }
        Some(node)
    }
}

class TrieNode {
    children: (TrieNode | null)[] = new Array(26).fill(null);
    isEnd: boolean = false;
}

class Trie {
    private root: TrieNode = new TrieNode();

    insert(word: string): void {
        let node = this.root;
        for (const c of word) {
            const idx = c.charCodeAt(0) - 97;  // 'a' = 97
            if (!node.children[idx])
                node.children[idx] = new TrieNode();  // create if missing
            node = node.children[idx]!;                 // move down
        }
        node.isEnd = true;                              // mark end of word
    }

    search(word: string): boolean {
        const node = this.traverse(word);
        return node !== null && node.isEnd;            // must be end-of-word
    }

    startsWith(prefix: string): boolean {
        return this.traverse(prefix) !== null;        // just needs to exist
    }

    // Helper: walk down the trie following each char
    private traverse(s: string): TrieNode | null {
        let node: TrieNode | null = this.root;
        for (const c of s) {
            const idx = c.charCodeAt(0) - 97;
            if (!node!.children[idx]) return null;
            node = node!.children[idx];
        }
        return node;
    }
}

Wildcard Search (DFS for '.' characters)

boolean searchWild(String word) {
    return dfs(root, word, 0);
}

boolean dfs(TrieNode node, String word, int i) {
    if (i == word.length()) return node.isEnd;

    char c = word.charAt(i);
    if (c == '.') {
        // wildcard: try every non-null child
        for (TrieNode child : node.children)
            if (child != null && dfs(child, word, i + 1))
                return true;
        return false;
    } else {
        int idx = c - 'a';
        if (node.children[idx] == null) return false;
        return dfs(node.children[idx], word, i + 1);
    }
}

func (t *Trie) SearchWild(word string) bool {
    return dfs(t.root, word, 0)
}

func dfs(node *TrieNode, word string, i int) bool {
    if i == len(word) {
        return node.isEnd
    }

    c := word[i]
    if c == '.' {
        // wildcard: try every non-nil child
        for _, child := range node.children {
            if child != nil && dfs(child, word, i+1) {
                return true
            }
        }
        return false
    }
    idx := c - 'a'
    if node.children[idx] == nil {
        return false
    }
    return dfs(node.children[idx], word, i+1)
}

def search_wild(self, word: str) -> bool:
    return self._dfs(self.root, word, 0)

def _dfs(self, node: TrieNode, word: str, i: int) -> bool:
    if i == len(word):
        return node.is_end

    c = word[i]
    if c == '.':
        # wildcard: try every non-None child
        for child in node.children:
            if child and self._dfs(child, word, i + 1):
                return True
        return False
    else:
        idx = ord(c) - ord('a')
        if node.children[idx] is None:
            return False
        return self._dfs(node.children[idx], word, i + 1)

pub fn search_wild(&self, word: String) -> bool {
    dfs(&self.root, word.as_bytes(), 0)
}

fn dfs(node: &TrieNode, word: &[u8], i: usize) -> bool {
    if i == word.len() {
        return node.is_end;
    }

    let c = word[i];
    if c == b'.' {
        // wildcard: try every non-None child
        for child in &node.children {
            if let Some(child_node) = child {
                if dfs(child_node, word, i + 1) {
                    return true;
                }
            }
        }
        return false;
    }
    let idx = (c - b'a') as usize;
    match &node.children[idx] {
        None => false,
        Some(child) => dfs(child, word, i + 1),
    }
}

searchWild(word: string): boolean {
    return this.dfs(this.root, word, 0);
}

private dfs(node: TrieNode, word: string, i: number): boolean {
    if (i === word.length) return node.isEnd;

    const c = word[i];
    if (c === '.') {
        // wildcard: try every non-null child
        for (const child of node.children)
            if (child && this.dfs(child, word, i + 1))
                return true;
        return false;
    } else {
        const idx = c.charCodeAt(0) - 97;
        if (!node.children[idx]) return false;
        return this.dfs(node.children[idx]!, word, i + 1);
    }
}

📝

Array vs HashMap children. Using TrieNode[26] gives O(1) child access and is fine when the character set is small (lowercase English). For larger alphabets (Unicode), use a HashMap<Character, TrieNode> to avoid wasting memory on empty slots.

Step 06

Visual Walkthrough

Let us trace through building a trie and searching it, showing the tree structure at every stage.

Words: ["tea", "ten", "to", "inn"]

Building the trie one word at a time, then performing lookups.

OPERATION	ACTION	TRIE PATHS	NODES CREATED
insert("tea")	Create t → e → a*	t-e-a*	3 new
insert("ten")	Reuse t → e, create n*	t-e-a* \| t-e-n*	1 new
insert("to")	Reuse t, create o*	t-e-a* \| t-e-n* \| t-o*	1 new
insert("inn")	New branch: i → n → n*	t-e-a* \| t-e-n* \| t-o* \| i-n-n*	3 new
search("tea")	Walk t → e → a, isEnd?	true (a has isEnd=true)	-
search("te")	Walk t → e, isEnd?	false (e has isEnd=false)	-
startsWith("te")	Walk t → e, exists?	true (node exists)	-

        Total nodes created: 8 (not 11). Shared prefixes saved 3 nodes.
      

💡

Notice the savings: "tea" and "ten" share the prefix "te", so those two characters are stored once, not twice. As the dictionary grows, more prefixes overlap. This is what makes tries space-efficient for large dictionaries with common prefixes.

Step 07

Common Problems

These are the classic LeetCode problems that use the trie pattern, listed in rough order of difficulty.

#208 Implement Trie (Prefix Tree) Medium

#720 Longest Word in Dictionary Medium

#648 Replace Words Medium

#677 Map Sum Pairs Medium

#211 Design Add and Search Words Data Structure Medium

#212 Word Search II Hard

💡

Practice tip: Start with #208 (direct implementation of the template). Then try #648 (walk the trie to find shortest matching prefix for each word). Once comfortable, tackle #211 (wildcard DFS) and #212 (trie + backtracking on a 2D board, one of the most popular hard trie problems).

Step 08

Interactive Demo

Type words to insert into a trie and watch the tree structure build visually. Then search for words or prefixes to see the traversal in action.

⚙ Trie Visualizer

Word

Operation

Batch Words (comma-separated)

Press "Batch Insert" or type a word and press "Run" to build the trie.

Insert words to build the trie, then search or check prefixes.

Step 09

Complexity Analysis

Insert / Search / Prefix

O(L)

Space

O(N * L)

Why O(L) per Operation?

Each operation (insert, search, startsWith) traverses at most L characters, where L is the length of the word or prefix. At each character, the work is O(1): check or create a child in a fixed-size array. Total: O(L) per operation — completely independent of dictionary size N.

Space: In the worst case (no shared prefixes), we store one node per character across all words. If N words each have average length L, the space is O(N * L). In practice, shared prefixes reduce this significantly.

Wildcard search: In the worst case with many '.' characters, the wildcard DFS may explore all branches, giving O(26^L) for a word of all dots. In practice, specific characters prune the search heavily.

⚡

Trie vs hash map for prefix operations: A hash set gives O(L) for exact search but O(N * L) for "does any word start with X?" (you must check every word). A trie gives O(L) for both. This is the fundamental advantage of the trie data structure.

Step 10

Key Takeaways

Each node is a character, each path is a word. A trie encodes strings as paths from root to end-of-word nodes. Shared prefixes share nodes, making storage efficient for dictionaries with common beginnings.

O(L) for insert, search, and prefix lookup. All three core operations are proportional to word length, not dictionary size. This is what makes tries ideal for prefix-heavy workloads like autocomplete and spell checking.

search() checks isEnd, startsWith() does not. The only difference between searching for an exact word and checking a prefix is the final isEnd flag. Both traverse the trie identically.

Wildcards use DFS branching at '.' characters. When a wildcard is encountered, recursively explore all children. For exact characters, follow the single matching child. This naturally extends the trie to support regex-like patterns.

Combines powerfully with backtracking and BFS. In problems like Word Search II (#212), a trie prunes the backtracking search on a 2D grid: instead of checking each word separately, you walk the trie as you explore the board, eliminating entire branches when the prefix does not exist.