What is a trie and when is it useful? | Interview Question

Q: What is a trie and when is it useful?

**Target Audience:** Beginners preparing for coding interviews — you need loops, classes and the idea of a tree. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Think about the contacts app on your phone. You type **"Ma"** and it instantly shows Maya, Mark and Martin. You type one more letter, **"Mar"**, and Maya disappears. The app is not reading through all of your 800 contacts on every key press. It behaves as if the names were filed in a cabinet of nested drawers: one drawer for every first letter, inside it a drawer for every second letter, and so o

The problem

Question presented to candidate: "What is a trie, and when would you use one instead of a hash set or a sorted list? Sketch the node structure and the basic operations in Python."

What a strong answer should cover:

A trie stores strings one character per edge; words with a common prefix share a path, and an end-of-word flag marks complete words.
insert, search and startsWith each cost O(L) in the word length, independent of how many words are stored, and search differs from startsWith only by the end-flag check.
When it wins: prefix queries (autocomplete, prefix counts), wildcard search, longest-prefix match; when it loses: exact-match-only lookups, where a hash set is smaller and simpler.
The memory trade-off: one node per distinct prefix, and per node either a fixed array (fast, wasteful) or a map (compact, slower).
Python details: children as a dict (any character), __slots__ to shrink nodes, dict.get for the walk, and sorted() because dicts keep insertion order, not alphabetical order.

Code / implementation expected: Optional — a Trie class with insert, search and startsWith in Python is a common follow-up.

trie
strings

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you need loops, classes and the idea of a tree.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Think about the contacts app on your phone. You type "Ma" and it instantly shows Maya, Mark and Martin. You type one more letter, "Mar", and Maya disappears. The app is not reading through all of your 800 contacts on every key press. It behaves as if the names were filed in a cabinet of nes

The solution is hidden so you can try first

13 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonTrie basics: insert, search, startsWith, prefix counts

Practice

PythonWords under a prefix, prefix sharing, trie vs hash set

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.