Why is a trie better than a hash map for prefixes?

A hash map hashes the whole key, so it can only answer exact-match questions; finding every word starting with a given prefix means scanning all N keys. A trie walks that prefix once in O(L), and every word below the node it lands on shares the prefix.

What is the end-of-word flag for?

It separates a stored word from a prefix you merely pass through. Inserting apple creates a node at app, so without the flag a lookup for app would wrongly report a stored word.

When is a hash map still the right answer?

When you only ever ask for exact keys. A hash map gives O(1) average lookup with far less memory, whereas a trie spends a node for every character of every distinct prefix.

Introduction to Tries

A preliminary look at why Prefix Trees (Tries) are superior to Hash Maps for certain string operations.

PREFIX "APP"

FOLLOW EDGE

→

LIST READS

TRIE STEPS

The list, filtered

APPLE

APPLY

APEX

BAT

CAT

Looking for words starting with "APP". The list holds 5; the trie holds one path per distinct prefix.

Character 'A': the list re-reads all 5 surviving words — 5 character reads so far. The trie follows one edge: 1 step, whatever the corpus size.

Intuition

If you want to search for the word "Apple" in a dictionary, you don't read every single word. you go to the 'A' section, then 'Ap', then 'App'...

A Trie mimics this process. It structures data by prefix, allowing us to traverse character by character, efficiently ignoring irrelevant branches.

Concept

Trie vs List:

List Search: Checks every word. O(N * L).
Trie Search: Follows a single path. O(L).

Tries are essentially N-ary trees where each edge represents a character.

How it Works

The visualizer simply compares:

Linear Scan: A red highlight checking every word "Apple" vs "Banana", "Apple" vs "Apricot"...
Prefix Traversal: A green path moving 'A' -> 'P' -> 'P'. It's much faster.

Step-by-Step Breakdown

1. Start at Root node.
2. For each character in the target string:
3. Check if a child node exists for that character.
4. If yes, move to it. If not, stop (not found).

When to Use

When you need prefix-based lookups.
Sorting strings (Radix Sort uses Trie logic).

When NOT to Use

If you only need exact match checks: a hash set is simpler. It is still O(L) per lookup, because hashing a string reads every character, so its advantage is simplicity and constant factors, not complexity.

How to Identify

"Starts with prefix...", "Autocomplete", "Spell check".