What is a trie?
A trie (prefix tree) stores strings as a tree of characters. Shared prefixes share the
same path from the root, so "cat" and "car" only fork after ca. Lookups cost
one step per letter — great for dictionaries, autocomplete, and word search.
- Root
- The empty starting node; every word hangs off it
- Child map / array
- Edges labeled by character —
Maporchildren[26] for a–z - End-of-word mark
- A flag on a node that says “a full word ends here”
- Prefix
- Any path from the root; not every prefix is a stored word
See it as shared paths
Insert "cat", then "car". The path c → a is built once and
reused — only the last letter forks. Watch each edge light up letter by letter.
That shared spine is the whole point of a trie: common prefixes cost memory once, and every later query walks the same edges.
Shared ca lights twice. Only the last letter forks.
Types of tries
Interview tries differ mainly in how children are stored, and whether single-child chains stay as one node per letter or get compressed.
An array of 26 slots is simple for lowercase English. A Map (or hash) fits
wider alphabets. A radix / compressed trie merges unary paths — optional polish.
Store answers “how are edges kept?” Shape answers “one letter or a chunk?”
How it lives in memory
In TypeScript a trie is nested objects on the heap. The root is a reference on the
stack; each children entry points at another node object. Inserting a word
allocates only the missing edges.
children—children—children—end—Start here. Each step highlights the TypeScript below.
Operations
Think of the trie as a hallway of letter doors. Tap Next on each demo to walk a path. For copy-paste TypeScript, open the Functions tab.
Insert
Follow each letter. Missing doors get new rooms. Mark the last room as a finished word.
Start at the root. Need an edge for c — create it.
Search word
Walk every letter. You only say “found” if the last room has the end-of-word mark.
Looking for "cat". Edge c exists — follow it.
Starts with / prefix
Same walk as search, but you stop when the path exists. The end mark does not matter.
Does any word start with "ca"? Follow c.
Delete (optional)
Clear the end mark. Prune a room only when it has no children and is not ending another word — leave shared prefixes alone.
Clear end on t. "cat" is no longer a stored word.
Autocomplete collect
Walk to the prefix node, then DFS every descendant that marks a finished word. That list is your suggestion set.
Reach the node for prefix "car".