Algorithms and data structures · Introductory

Tries: sharing common prefixes in a search tree

Follow characters through shared prefixes and distinguish full-key membership from prefix existence.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Represent a key by its sequence of characters
  2. Separate a prefix from a stored complete key
  3. Choose an alphabet and a child representation
  4. Use compression when paths are sparse
  5. Ask Logeia about this articleCheck your understanding

Represent a key by its sequence of characters

A trie stores strings by sharing their prefixes. In a simple character-edge representation, following c, then a, then t from the root represents cat. The keys cat and car share the path for ca. Rather than repeatedly comparing complete candidate strings, lookup chooses the edge corresponding to the next character. Under an assumption of constant-time child selection, finding a key of length L takes O(L). The bound is expressed in key length, so it should not be casually described as independent of the input size.

Separate a prefix from a stored complete key

A trie containing cat and car has a path for ca, but that does not prove that ca was inserted as a complete key. A terminal marker or stored value distinguishes the end of an actual key from an intermediate prefix. To enumerate words beginning with ca, first reach that prefix node and then traverse its descendants. Reaching the prefix and producing all matching results are different tasks. An autocomplete request with many matches must pay for visiting and outputting those matches, even if locating the prefix is quick.

Choose an alphabet and a child representation

An array of child references for every possible symbol makes edge selection straightforward but can waste substantial space on absent edges. Storing only existing edges in a dictionary or a search tree changes both memory use and lookup costs. For Unicode text, decide whether edges represent bytes, code points, or another unit; these are not identical to displayed characters. Case folding and normalization also need explicit rules. Otherwise, visually similar strings can follow distinct paths or a prefix can be interpreted differently by indexing and querying code.

Use compression when paths are sparse

A compressed trie can combine a chain of single-child nodes into a labeled edge, reducing node and reference overhead. Insertions and searches must then handle a match that ends inside such an edge. Tries are useful for prefix dictionaries, autocomplete, and bit-prefix routing structures, but a hash table may be simpler for short exact-key lookups with no prefix operations. Compare prefix sharing, alphabet size, storage representation, key length, and output volume. The shared-prefix idea explains the structure, while those workload details determine whether it is a good implementation choice.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 9

Choose a learning path