Trie or hash set?

Strings and tries Mid-level Python 3.13+ Reviewed By Best Latest Apps

Pick the fix

You must check if each of a million incoming words is in a stored list of 50,000 words. Nothing else is needed. What should you use?

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A A set of the stored words

Right: exact membership in O(L) with the least effort and memory.

When only exact lookups are needed, the simplest hashed structure wins; a trie earns its cost through prefix questions.

Why not the others?
  • B A trie of the stored words. It works, but prefix features are unused and memory is higher.
  • C Sort the stored words and scan from the start each time. Scanning is O(n) per word.

30-second answer

A set answers 'is this exact word stored?' in O(L) (hashing the word) with less memory. A trie also answers prefix questions: how many words start with p, list them, autocomplete, wildcard lookups, and the longest stored prefix of a query, all in time proportional to the prefix. Pick a set for exact membership only; a trie when prefixes matter.

Practise saying it · 30 s. No recording, just a timer

Compare tries and hash sets.

Say your answer out loud, then check which of these points you covered:

  • Set: exact lookups
  • Trie: prefix questions
  • Memory trade-off

Deep dive

Tries can use more memory: one node per letter unless prefixes are shared heavily.

A sorted list with binary search covers many prefix questions with very little memory.

Search engines use inverted indexes (word → documents) rather than tries for full-text search.

Common mistakes

  • Building a trie just to test exact membership.
  • Forgetting the end-of-word marker in a trie.

Senior take & follow-ups

Choose based on the questions you must answer, and say so.

Follow-up questions

Think of your answer first, then open the hint.

  1. What is a compressed trie?

    Show hint

    One where chains of single-child nodes are merged into one edge holding a string, saving memory.

  2. How do search engines find documents by word?

    Show hint

    An inverted index maps each term to a list of documents; tries may index the term dictionary.

Similar on Backend: Search with Elasticsearch or OpenSearch The Backend page covers inverted indexes for full-text search across documents; this page compares tries and sets for word lookups inside one program.

What each operation costs: Trie · KMP Algorithm · Rabin Karp · String Matching

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.