Skip to content
Tutorials Center
My learning

Topics

Lesson 112 of 225 ยท Tries and Range Queries

Tries

Learn the trie (prefix tree) in Python: insert, search and starts_with, dict vs array children, delete, counting words by prefix, memory use and complexity.

Imagine a phone keyboard suggesting words as you type "pro". It must find every word starting with those three letters, instantly, among hundreds of thousands. Scanning the whole dictionary on every keystroke is too slow. A hash table can tell you whether "pro" is a word, but it cannot tell you which words start with "pro". A sorted list plus binary search can, but it is awkward to update.

A trie (pronounced "try", from retrieval), also called a prefix tree, is built for exactly this. It stores strings letter by letter along the edges of a tree, so words that share a prefix share a path. Searching for a word or prefix costs time proportional to its length, no matter how many words are stored.

The idea

Each node represents a prefix. Each edge is labeled with one character. A node is flagged if the path from the root to it spells a complete word.

Here is a trie containing car, card, care, cat and dog. Nodes marked * end a word:

TEXT
(root)
 โ”œโ”€โ”€ c
 โ”‚    โ””โ”€โ”€ a
 โ”‚         โ”œโ”€โ”€ r*  ("car")
 โ”‚         โ”‚    โ”œโ”€โ”€ d*  ("card")
 โ”‚         โ”‚    โ””โ”€โ”€ e*  ("care")
 โ”‚         โ””โ”€โ”€ t*  ("cat")
 โ””โ”€โ”€ d
      โ””โ”€โ”€ o
           โ””โ”€โ”€ g*  ("dog")

Notice that car, card, care and cat share the path c -> a. Also notice that car is both a word and a prefix of other words, which is why we need the end-of-word flag: reaching a node does not mean you found a word.

The operations

  • insert(word): walk from the root, creating a child node for each missing character, then flag the last node.
  • search(word): walk from the root following each character; fail if an edge is missing; succeed only if the last node is flagged.
  • starts_with(prefix): the same walk, but succeed as long as the walk does not fail (no flag needed).

All three take O(L) time, where L is the length of the string.

A trie from scratch

The simplest Python trie uses a dictionary per node, mapping a character to the child node.

Python A trie with insert, search and starts_with

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the results for "ca": search says False (it is not a word) but starts_with says True (it is a prefix of several). And the empty string is a prefix of everything, but not a word unless you inserted it.

Tracing an insertion

Let's insert "cab" into the trie above, step by step:

TEXT
start at root
'c' -> child exists, move to c
'a' -> child exists, move to a
'b' -> a has children r and t only, create b
mark b as a word

Only one new node was created, because "ca" was already there. Inserting "cat" again would create no node at all. The number of nodes grows with the number of distinct prefixes, not with the number of words.

Listing all words under a prefix

Walking to the prefix node and then exploring its subtree (a depth-first traversal) collects every word that starts with it. Visiting children in alphabetical order also returns the words sorted.

Python Words with a given prefix, in sorted order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting and deleting

Often you want more than yes or no. Store a counter on each node:

  • pass_count: how many inserted words go through this node. That answers "how many words start with this prefix?" in O(L).
  • end_count: how many times a word ends here (handles duplicates).

Deleting a word means unmarking its last node and then pruning nodes that are no longer useful (no children and not the end of another word). The easiest way is recursion that returns whether the child can be removed.

Python Counts and deletion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The pass_count trick also makes deletion tidy: when a node's count drops to zero, nothing below it is needed, so we cut the whole branch at once.

Children as an array

A dictionary per node is flexible: it handles any alphabet, including Unicode. If you know the alphabet is small and fixed, such as a-z, a node can hold a fixed array of 26 slots instead. The child for letter ch lives at index ord(ch) - ord("a").

TEXT
node.children = [None, None, <node>, None, ... 26 slots]
                  a     b      c     d
  • Speed: index lookup, no hashing. In languages like C, C++ and Java this is the standard choice.
  • Memory: every node pays for 26 slots even if it has one child. For a sparse trie this wastes a lot.

In Python, a list of 26 references costs more memory than a small dict whenever a node has few children, so the dict version usually wins. Compare them yourself.

Python Dict children vs array children

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity

Let L be the length of the word, N the number of words and A the alphabet size.

Operation Time Notes
insert O(L) One step per character
search / starts_with O(L) Independent of N
delete O(L) With counters or pruning
list all words under a prefix O(L + size of subtree) Output-sensitive
Space O(total characters) worst case Shared prefixes reduce it; array nodes multiply by A

Compare with a hash set of words: search is also O(L) there (hashing reads every character), but a set cannot answer prefix queries without scanning everything. A trie's advantage is prefix operations and ordered output; its price is memory.

Memory and compressed variants

A trie can use a lot of memory: one node object per distinct prefix, each with a dict. Long chains of nodes with a single child are common (think of the unique ending of a word like "extraordinary"). Fixes:

  • Radix tree (compressed trie): merge chains into one edge labeled with a string. You will see this in Trie Applications.
  • Use __slots__ on node classes to shrink each object.
  • DAWG / minimal automaton: also share common suffixes; great for static dictionaries.

When to use a trie

Choose a trie when you need:

  • autocomplete, spell-check suggestions, prefix search;
  • "does any word start with ...?" checks (word games, dictionary lookups);
  • longest-common-prefix and IP routing (longest prefix match);
  • many string queries over a fixed dictionary, where per-query time must not depend on the number of words.

Avoid it when you only need exact lookup (use a set or dict), when strings are very long and sparse (memory), or when the data fits in a sorted list and bisect is enough: a sorted list can also find all words with a prefix by two binary searches.

Common mistakes

  • Treating "reached the node" as "found the word". Always check the end-of-word flag in search.
  • A mutable default argument such as def __init__(self, words=[]): all instances would share one list. Use None and create the list inside.
  • Forgetting the empty string. The root itself can be a word if you insert "".
  • Case and character handling. An array trie crashes on characters outside its alphabet; normalize input first (word.lower()).
  • Deleting without pruning, which leaves unused nodes behind and wastes memory.
  • Recursion depth. A recursive walk is as deep as the longest word; for very long strings use an explicit loop or stack.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the time complexity of searching for a word of length L in a trie holding N words?

    The search follows one edge per character and never looks at the other words, so N does not matter.
  2. 2. A trie holds only the word 'car'. What do search('ca') and starts_with('ca') return?

    'ca' is a prefix of 'car' but not a stored word, so the end-of-word flag is missing while the path exists.
  3. 3. Why does a trie need an end-of-word flag on nodes?

    Without the flag you could not tell whether 'car' was inserted or is merely the beginning of 'card'.
  4. 4. What is the main drawback of a trie compared with a hash set of words?

    A trie allocates a node per distinct prefix, often with a dictionary or array per node, which costs far more than storing the strings in a set.
  5. 5. How can a pass_count stored on each node be used?

    pass_count records how many inserted words go through the node, so the node reached by a prefix answers the prefix-count query directly.

Summary

  • A trie (prefix tree) stores strings character by character; words with a common prefix share a path.
  • insert, search and starts_with all take O(L) time for a string of length L, independent of the number of words.
  • Mark the end of words with a flag (or a counter): a node can be both a prefix and a word.
  • Use dict children for flexibility; fixed arrays only when the alphabet is small and the trie is dense.
  • Tries shine at prefix queries and sorted listing, but cost memory; compressed (radix) tries and DAWGs reduce it.
  • Counters on nodes give prefix counts and make deletion simple.

Next: Trie Applications