trie

A trie, also called a prefix tree or digital tree, is a tree data structure that stores a set of strings character by character, so keys that start with the same characters share the same path from the root.

Each edge carries a single character, so the path from the root down to a node spells out one prefix, and the node itself stores no key. A flag on the node records whether the prefix ending there is a complete key or only a waypoint toward longer ones. Keys that start alike share the same upper edges and branch apart only where they first differ.

Searching, inserting, and deleting each follow one edge per character, so their time complexity tracks the length of the key rather than the number of keys stored. That means O(L) work for a key of length L, independent of the n keys already present, where a balanced binary search tree needs O(log n) comparisons of whole strings.

Beyond plain lookup, the layout answers questions a hash table cannot:

  • Prefix search: every key starting with a given prefix lies in the subtree below that prefix, the property behind autocomplete and typeahead.
  • Ordered traversal: visiting each node’s children in alphabetical order emits the keys in lexicographic order.
  • Longest-prefix match: the deepest marked node along a path gives the longest stored key that prefixes the query, which is how routers pick the most specific matching network in an IP routing table.

The trie below holds seven keys. Typing a prefix into it follows a single edge per character from the root and then lights up the subtree that holds every key starting with that prefix.

Interactive diagram — enable JavaScript to view.

The trade-off is memory, because an array-based trie reserves a child slot per alphabet symbol at every node, and even a dictionary-based one pays for a separate node per character. Compressed variants such as the radix tree merge chains of single-child nodes into one labeled edge, and a Patricia trie applies that idea to bitwise keys. Edward Fredkin coined the name in 1960, taking it from the middle syllable of “retrieval”.

Common Python Data Structures (Guide)

Tutorial

Common Python Data Structures (Guide)

In this tutorial, you'll learn about Python's data structures. You'll look at several implementations of abstract data types and learn which implementations are best for your specific use cases.

basics data-structures python stdlib

For additional information on related topics, take a look at the following resources:

Have a question about this? Mentor AI can show you examples, compare related terms, and point you to tutorials.

  • Ask Mentor AI
  • Pick a question and Mentor AI takes it from here.
By Martin Breuss • Updated Oct. 5, 2026
Computer Science Glossary Share Feedback