Tries

nice-to-have mid - part of Skills & Topics - Senior SWE Roadmap - related: Hashing and Hash Maps - Arrays & Strings - Sorting and Searching Algorithms

Why this matters / recognition signals

A trie (prefix tree) is the right structure when the expensive part of the problem is not equality, but shared prefixes. Instead of storing each word as an isolated key, a trie stores them character by character so that lookup, prefix matching, and autocomplete can reuse the same path.

Reach for this when the problem says:

• “starts with this prefix” / “autocomplete” / “typeahead”
• “find words with a shared prefix”
• “dictionary of strings with insert/search/delete”
• “longest common prefix”
• “word search with many dictionary lookups”

Core idea: one node per prefix

Each edge is a character. Following edges from the root spells a prefix; a special terminal marker says that prefix is also a full word.

flowchart TD
    R["root"] --> C["c"]
    C --> A["a"]
    A --> R1["t*
(cat)"]
    A --> R2["r*
(car)"]
    C --> O["o"]
    O --> N["n"]
    N --> E["e*
(cone)"]

The shared prefix c -> a is stored once, then branches into t, r, and o. That is the whole win: if many strings begin with the same prefix, the trie avoids re-reading the same characters repeatedly.

Worked example: inserting words

Insert cat, car, and cone.

Word	Path created or reused	Terminal node
cat	c → a → t	mark t as end of word
car	c → a reused, then r	mark r as end of word
cone	c reused, then o → n → e	mark e as end of word

Now startsWith("ca") just walks c -> a and succeeds without exploring the whole dictionary.

Java implementations

Trie with insert, search, and prefix check

import java.util.HashMap;
import java.util.Map;
 
class Trie {
    protected static class Node {
        Map<Character, Node> children = new HashMap<>();
        boolean isWord;
    }
 
    protected final Node root = new Node();
 
    public void insert(String word) {
        Node node = root;
        for (char ch : word.toCharArray()) {
            node = node.children.computeIfAbsent(ch, key -> new Node());
        }
        node.isWord = true;
    }
 
    public boolean search(String word) {
        Node node = walk(word);
        return node != null && node.isWord;
    }
 
    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }
 
    protected Node walk(String text) {
        Node node = root;
        for (char ch : text.toCharArray()) {
            node = node.children.get(ch);
            if (node == null) {
                return null;
            }
        }
        return node;
    }
}

Autocomplete by DFS from a prefix node

import java.util.ArrayList;
import java.util.List;
 
class AutocompleteTrie extends Trie {
    public List<String> complete(String prefix) {
        List<String> result = new ArrayList<>();
        Node node = walk(prefix);
        if (node == null) {
            return result;
        }
        collect(node, new StringBuilder(prefix), result);
        return result;
    }
 
    private void collect(Node node, StringBuilder path, List<String> result) {
        if (node.isWord) {
            result.add(path.toString());
        }
        for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
            path.append(entry.getKey());
            collect(entry.getValue(), path, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

The exact autocomplete API varies, but the pattern is always the same: walk to the prefix node in O(L), then DFS downward to collect completions.

Python implementations

Trie with insert, search, and prefix check

class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.is_word = False
 
 
class Trie:
    def __init__(self) -> None:
        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_word = True
 
    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_word
 
    def starts_with(self, prefix: str) -> bool:
        return self._walk(prefix) is not None
 
    def _walk(self, text: str) -> TrieNode | None:
        node = self.root
        for ch in text:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Collecting completions from a prefix

def autocomplete(trie: Trie, prefix: str) -> list[str]:
    node = trie._walk(prefix)
    if node is None:
        return []
 
    result: list[str] = []
 
    def dfs(curr: TrieNode, path: list[str]) -> None:
        if curr.is_word:
            result.append(prefix + "".join(path))
        for ch, child in curr.children.items():
            path.append(ch)
            dfs(child, path)
            path.pop()
 
    dfs(node, [])
    return result

Common pitfalls

• Treating a trie like a hash map replacement for exact lookup only: for exact word membership, a hash set is usually simpler and faster in practice. Use a trie when prefixes matter.
• Forgetting the terminal marker: without isWord, search("car") and startsWith("car") become indistinguishable.
• Using too much memory for sparse alphabets: a fixed 26-way array per node is fast for lowercase English, but wasteful for large or sparse character sets.
• Misjudging complexity: trie operations are O(L) for a string of length L, not O(1); the payoff is that you avoid scanning every stored word.

Practice problems

• Implement Trie / Prefix Tree
• Replace Words
• Word Search II
• Longest Common Prefix
• Search Suggestions System

Interview angles

• “Why use a trie instead of a hash set?” - because a hash set answers exact membership; a trie answers prefix queries and can enumerate completions efficiently.
• “What is the time complexity of trie operations?” - O(L) for insert/search/prefix lookup, where L is the length of the string.
• “When is a trie overkill?” - if you only need exact lookup and not prefix behavior, a hash table is usually the better tool.