What Is a Trie?

A trie (pronounced "try") is a tree-like data structure that stores strings character by character. Each node represents a single character, and paths from the root to nodes form prefixes of the stored words. The root node is empty — it represents the empty string.

🔤
Why "trie"?
From the word "retrieval" — a tree built for fast prefix lookups

Unlike a hash map that stores complete words, a trie shares prefixes. The words "app", "apple", and "apt" share the path a → p. This shared structure is what makes tries efficient for prefix queries: instead of scanning every word in a dictionary, you walk down the tree one character at a time.

The key insight: common prefixes are stored once. If you have 10,000 words starting with "pre", the trie stores "p → r → e" just once and branches from there. This makes prefix-based operations — autocomplete, spell checking, IP routing — extremely fast.

Trie Built from ["app", "apple", "apt", "bat", "bar"]

root a b a b p a p a p t t r p t t r l l e e app apt bat bar apple
Internal node End of word (is_end = True)

Notice how "app" and "apple" share the path root → a → p → p. The green nodes mark where complete words end. The node for the second "p" is green because "app" is a word, even though the path continues to "apple".

Shared prefixes save space:
Without a trie, storing ["app", "apple", "apt"] would repeat "a" and "p" multiple times. The trie stores each unique character path once. The trade-off: each node needs a children dictionary, so tries use more memory per character than a flat list — but they make prefix queries instant.

TrieNode Structure

Every node in a trie has two things: a dictionary of child nodes (one entry per character that continues from here) and a boolean flag indicating whether this node marks the end of a complete word.

trie_node.py The building block

Why a dictionary for children?

  • Flexibility: A dictionary maps each character to its child node. You don't need to pre-allocate 26 slots (or more for Unicode) — only characters that actually appear get stored.
  • Lookup: Checking if a character exists is O(1) on average with a hash map.
  • Alternative: Some implementations use a fixed-size array of 26 entries (for lowercase English letters). This trades memory for slightly faster lookups since array indexing is faster than hashing.
Interview tip:
When discussing tries in an interview, mention the dictionary-based approach first (it's clean and Pythonic), then note that a fixed-size array can be faster for known character sets. Interviewers love seeing that you understand the trade-off.

Implement Trie — Insert, Search, StartsWith

The Trie class wraps a root TrieNode and provides three core operations. This is LeetCode 208 — one of the most frequently asked data structure design problems.

trie.py Core operations — O(m) each, where m = word length
Output
True False True True False True

How each method works

  • insert(word) — Walk character by character from the root. If a child for the current character doesn't exist, create a new TrieNode. After the last character, mark is_end = True.
  • search(word) — Walk the trie following the word's characters. If any character is missing, return False. If you reach the end, check is_end — the word exists only if this node marks a complete word.
  • starts_with(prefix) — Same walk as search, but you don't check is_end. If you can follow all characters without hitting a dead end, the prefix exists.
  • _find(prefix) — Shared helper that walks the trie and returns the node at the end of the prefix (or None). Both search and starts_with use this to avoid code duplication.
Time complexity:
All three operations are O(m) where m is the length of the word or prefix. This is independent of how many words are stored — whether your trie has 10 words or 10 million, lookup time depends only on the word length.

Autocomplete — Find All Words with a Prefix

This is where tries truly shine. Given a prefix, return all stored words that start with it. This is exactly what happens when you type in a search bar and see suggestions appear.

autocomplete.py DFS from the prefix node to collect all completions
Output
['app', 'apple', 'application', 'approve'] ['app', 'apple', 'application', 'approve', 'apt'] ['bat', 'bar'] []

How autocomplete works

  1. Navigate to the prefix node — Use _find(prefix) to walk to the node representing the last character of the prefix. If the prefix doesn't exist in the trie, return an empty list.
  2. DFS from that node — From the prefix node, explore all descendants using depth-first search. Every time you reach a node where is_end = True, you've found a complete word — add prefix + path to results.
  3. Build the path as you go — Each recursive call appends the current character to the path string, building up the suffix that completes the word.
Performance note:
Autocomplete is O(m + k) where m is the prefix length and k is the total number of characters in all matching words. In a real search engine, you'd limit results to the top N suggestions (by frequency or relevance) to avoid returning thousands of matches.

Space vs Time Trade-off

Tries trade memory for speed. Understanding this trade-off is critical for interviews — it shows you think beyond just time complexity.

⚖
Trie vs Hash Set
When does each win?
  • Hash Set search: O(m) average (hash the word, then compare) — but no prefix support. To find all words starting with "app", you'd scan every word in the set.
  • Trie search: O(m) guaranteed — walk m characters down the tree. Plus, prefix queries like starts_with and autocomplete are natural and fast.
  • Memory: A trie node stores a dictionary of children + a boolean. For sparse data (few shared prefixes), this overhead can exceed a hash set. For dense data (many shared prefixes), the trie can actually use less total space than storing full strings.

When tries use more memory

Consider storing ["cat", "dog", "fish"]. These words share no prefixes, so the trie creates one node per character — 10 nodes, each with a dictionary. A hash set stores 3 strings with less overhead. Tries shine when there's heavy prefix sharing: storing 10,000 English words starting with "un-" reuses the u → n path 10,000 times.

Rule of thumb:
Use a trie when you need prefix operations (autocomplete, prefix count, longest common prefix). Use a hash set when you only need exact membership checks and want minimal memory.

When to Use Tries

Tries appear across system design and coding interviews. Recognise these patterns and you'll know when to reach for a trie:

🎯
Pattern recognition
Spot these scenarios in interviews
  • Autocomplete / Type-ahead: "Design a search suggestion system" — trie is the textbook answer. Google, YouTube, and Amazon all use trie-like structures for search suggestions.
  • Spell checker: Check if a word exists in a dictionary, suggest corrections by exploring nearby paths in the trie.
  • IP routing: Routers use tries to match IP addresses against routing tables. The longest prefix match determines where a packet goes.
  • Word games: Scrabble solvers and Boggle checkers use tries to quickly validate words and prune invalid paths on the board.
  • Prefix count: "How many words in the dictionary start with 'pre'?" — walk to the "pre" node and count descendants.
  • Longest common prefix: Walk the trie from the root until a node has more than one child — that path is the longest shared prefix (LeetCode 14).
Interview tip:
If a problem mentions "prefix", "dictionary of words", or "autocomplete", a trie is almost certainly the right approach. Even if the brute-force solution uses a hash set, mentioning the trie optimization shows depth of knowledge.

Try It Yourself

Implement a Trie with Insert, Search, StartsWith

Complete the Trie class below. Implement insert, search, and starts_with. The test cases will verify your implementation.

Challenge

Word Search II (LeetCode 212)
Your task:

Given a 2D board of characters and a list of words, find all words that can be formed by sequentially adjacent cells (horizontally or vertically). Each cell may only be used once per word.

Example: Board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], Words = ["oath","pea","eat","rain"]. Answer: ["oath","eat"].

Why a trie? Instead of searching the board for each word separately, build a trie from the word list and search the board once — pruning branches that don't match any prefix in the trie.

Build a trie from the words list. Then DFS from every cell on the board. At each cell, check if the current character exists as a child in the current trie node. If yes, move to that child and explore all 4 neighbours (marking cells as visited). If the trie node has is_end = True, you found a word — add it to results and set is_end = False to avoid duplicates. Backtrack by unmarking the cell when you return.

Quiz

Question 1 of 5
What does each node in a trie represent?
Question 2 of 5
What is the time complexity of searching for a word of length m in a trie containing n words?
Question 3 of 5
What distinguishes search("app") from starts_with("app") in a trie?
Question 4 of 5
Which of these is NOT a common use case for tries?
Question 5 of 5
When would you prefer a hash set over a trie for storing strings?
0
/5
Great work! You understand tries.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

You've mastered prefix trees.
Now build the career they power.

Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.

Explore our AI-era courses →