Overview

A trie stores a set of strings character by character. The root represents the empty string, each edge adds one character, and a flag marks nodes where a complete word ends. Because words with a common prefix share the same path, checking whether any word starts with "algo" costs four steps no matter how many words are stored.

Tries shine when you have many queries against one dictionary: autocomplete suggestions, spell checking, replacing words by their roots, or searching a grid for many words at once (build one trie, run one DFS). A binary version — a trie over the bits of numbers — finds the maximum XOR pair in linear time.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Insert / search / startsWithO(L) per word
Build from wordsO(total characters)
SpaceO(total characters × alphabet) worst case with arrays

Patterns to recognise

Prefix lookup

Use it for: Autocomplete, search suggestions, replace words.

Walk to the prefix node, then collect or check below it.

Many words, one search

Use it for: Word Search II, concatenated words.

Build one trie from all words and traverse it alongside the search.

Bitwise greedy

Use it for: Maximum XOR of two numbers.

For each bit, prefer the child that differs from the current number.

Code template

Trie with insert, search and startsWith
class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['#end'] = True

    def _walk(self, text):
        node = self.root
        for ch in text:
            if ch not in node:
                return None
            node = node[ch]
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and '#end' in node

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

Common mistakes

  • Forgetting the end-of-word flag makes every prefix look like a word.
  • A 26-slot array per node is fast but memory hungry; use a hash map for large alphabets.
  • In Word Search II, remove found words (or prune empty branches) to avoid duplicates and timeouts.

Quick check

Three questions on Tries. Get all three right to earn +15 XP.

  1. Looking up a word of length L in a trie costs:

  2. What does the end-of-word flag on a trie node tell you?

  3. Which task is a trie especially good at?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Tries?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor