Tries

Updated Nov 16, 2026 · 5 min read
On this page

    Type "ca" into a search box and it suggests "car", "cart", "cat" before you finish. Doing that with a list of a million words means checking every word for the prefix on every keystroke. A hash set can't help either: it only answers "is this exact word here?". A trie stores words by their shared prefixes, so finding everything that starts with "ca" costs two steps plus the size of the answer, no matter how many words there are.

    This page covers both the data structure and the pattern: the Trie problems in the Problems section build on it directly.

    How it works

    One letter per edge, shared prefixes

    Words that start the same way share the same path from the root; a flag marks the nodes where a word ends.
    Words that start the same way share the same path from the root; a flag marks the nodes where a word ends.

    A trie (also called a prefix tree) is a tree where each edge stands for one character. The path from the root to a node spells a prefix. Each node holds:

    • children: a map from character to child node;
    • is_end: a flag saying "a word ends here".

    The flag matters: "car" and "cart" share the path c → a → r, and only the flag on r tells you that "car" itself is a word.

    Insert, search, prefix search

    All three walk down from the root one character at a time:

    • Insert: follow existing edges, creating nodes where they're missing; set is_end on the last node.
    • Search(word): follow the edges; if one is missing, the word isn't there. At the end, return is_end.
    • StartsWith(prefix): the same walk, but succeed as soon as the prefix's last node exists.
    A prefix search walks one node per character; every word below the last node shares that prefix.
    A prefix search walks one node per character; every word below the last node shares that prefix.

    Each operation costs O(L), where L is the length of the word or prefix, independent of how many words the trie holds.

    Storing children

    A hash map works for any alphabet and uses memory only for real edges; a fixed array of 26 is faster for lowercase letters.
    A hash map works for any alphabet and uses memory only for real edges; a fixed array of 26 is faster for lowercase letters.

    Operations and costs

    OperationTrieHash set of words
    Insert a word of length LO(L)O(L) to hash it
    Exact searchO(L)O(L)
    Does any word start with this prefix?O(L)O(n · L): check every word
    List all words with a prefixO(L + size of the output)O(n · L)
    MemoryO(total characters), shared prefixes stored onceO(total characters)

    When to reach for it

    • Prefix questions: autocomplete, search suggestions, "does any word start with…".
    • Many words searched in a grid or text at once: build a trie of the words and walk it during a single DFS of the board, instead of searching for each word separately (Word Search II).
    • Wildcards: a . that matches any letter becomes "try every child" at that position.
    • Replace words by their shortest root: walk the trie and stop at the first is_end.
    • Bitwise tries (one edge per bit) answer "maximum XOR with this number" questions. Rare, but worth knowing exists.

    If you only need exact lookups, a hash set is simpler and just as fast.

    Example

    A trie with insert, search and prefix search:

    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:
                node = node.children.setdefault(ch, TrieNode())
            node.is_end = True
    
        def _walk(self, s):
            node = self.root
            for ch in s:
                node = node.children.get(ch)
                if node is None:
                    return None
            return node
    
        def search(self, word):
            node = self._walk(word)
            return node is not None and node.is_end
    
        def starts_with(self, prefix):
            return self._walk(prefix) is not None
    class Trie {
        private static class Node {
            Map<Character, Node> children = new HashMap<>();
            boolean isEnd;
        }
        private final Node root = new Node();
    
        public void insert(String word) {
            Node node = root;
            for (char ch : word.toCharArray()) {
                node = node.children.computeIfAbsent(ch, k -> new Node());
            }
            node.isEnd = true;
        }
        private Node walk(String s) {
            Node node = root;
            for (char ch : s.toCharArray()) {
                node = node.children.get(ch);
                if (node == null) return null;
            }
            return node;
        }
        public boolean search(String word) {
            Node node = walk(word);
            return node != null && node.isEnd;
        }
        public boolean startsWith(String prefix) {
            return walk(prefix) != null;
        }
    }
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        bool isEnd = false;
    };
    
    class Trie {
        TrieNode* root = new TrieNode();
        TrieNode* walk(const string& s) {
            TrieNode* node = root;
            for (char ch : s) {
                auto it = node->children.find(ch);
                if (it == node->children.end()) return nullptr;
                node = it->second;
            }
            return node;
        }
    public:
        void insert(const string& word) {
            TrieNode* node = root;
            for (char ch : word) {
                if (!node->children.count(ch)) node->children[ch] = new TrieNode();
                node = node->children[ch];
            }
            node->isEnd = true;
        }
        bool search(const string& word) {
            TrieNode* node = walk(word);
            return node && node->isEnd;
        }
        bool startsWith(const string& prefix) { return walk(prefix) != nullptr; }
    };
    type TrieNode struct {
        children map[rune]*TrieNode
        isEnd    bool
    }
    
    type Trie struct{ root *TrieNode }
    
    func NewTrie() *Trie {
        return &Trie{root: &TrieNode{children: map[rune]*TrieNode{}}}
    }
    
    func (t *Trie) Insert(word string) {
        node := t.root
        for _, ch := range word {
            next, ok := node.children[ch]
            if !ok {
                next = &TrieNode{children: map[rune]*TrieNode{}}
                node.children[ch] = next
            }
            node = next
        }
        node.isEnd = true
    }
    
    func (t *Trie) walk(s string) *TrieNode {
        node := t.root
        for _, ch := range s {
            next, ok := node.children[ch]
            if !ok {
                return nil
            }
            node = next
        }
        return node
    }
    
    func (t *Trie) Search(word string) bool {
        node := t.walk(word)
        return node != nil && node.isEnd
    }
    
    func (t *Trie) StartsWith(prefix string) bool { return t.walk(prefix) != nil }

    Time: O(L) per call. Space: O(total characters inserted). After inserting car, cat, cart, do and dog: search("car") is true, search("ca") is false (no word ends there), starts_with("ca") is true.

    Common mistakes

    • Forgetting the end flag. Without it, every prefix of a word looks like a word.
    • Search vs. starts-with. They share the walk; only the final check differs.
    • Rebuilding the trie per query. Build once, query many times; that's the whole point.
    • Collecting suggestions from the root. Walk to the prefix's node first, then DFS only below it.
    • Memory on huge inputs. An array of 26 children per node is fast but heavy; use a map when the alphabet is large or sparse.
    • In Word Search II, not pruning. Remove a word's end flag (or the leaf) after finding it, so you don't report it twice and you stop exploring dead branches.

    Say this in the interview

    • "A hash set can tell me if a word exists, but not if any word starts with a prefix. A trie answers both in O(length of the prefix)."
    • "I'll store children in a map and an is-end flag on each node, so 'car' and 'cart' can share the path."
    • "Instead of searching the board once per word, I'll put all the words in a trie and do a single DFS that follows the trie as it goes."

    Used in