Trie

A trie, or prefix tree, is a tree that stores a set of strings by their characters: each edge is labelled with a character, each key is spelled by the path from the root to a node, and keys with a common prefix share the nodes of that prefix. Looking up or inserting a key takes time proportional to its length, independent of the number of keys stored, and no two keys are ever compared with each other. All keys that begin with a given prefix lie in one subtree, in sorted order, which makes tries the natural structure for autocompletion, dictionaries and longest-prefix matching^[4]. Radix and Patricia trees compress chains of nodes with a single child^[3], and reading integers bit by bit gives tries for integer keys, such as the Patricia trees used for maps in functional languages^[5].

Each node of a trie stands for the string spelled by the path from the root to it, and records whether that string is one of the keys. A node has at most one child per character of the alphabet. The keys a, i, in, inn, to, tea, ted and ten give:

The name comes from "retrieval"; Fredkin, who introduced it, pronounced it "tree", and it is now usually pronounced "try" to distinguish it from trees in general^[2].

Looking up a key follows one edge per character, and fails as soon as an edge is missing. Inserting follows the existing edges and creates nodes for the rest of the key. Deleting unmarks the key's node and removes nodes that have become useless. For a key of length $k$, each operation visits $k+1$ nodes; with children stored in an array indexed by character each step is constant time, and with a balanced search tree of children it is $O(\log \sigma )$ for an alphabet of size $\sigma$:

A balanced binary search tree on the same keys makes $O(\log n)$ comparisons, each of which may read up to $k$ characters. The trie reads each character of the key once.

(* A persistent trie: each node records whether a key ends there, and maps
   the next character to a child. *)
module CMap = Map.Make (Char)
 
type t = { final : bool; children : t CMap.t }
 
let empty = { final = false; children = CMap.empty }
 
let insert word t =
  let n = String.length word in
  let rec go i t =
    if i = n then { t with final = true }
    else
      let child = Option.value (CMap.find_opt word.[i] t.children) ~default:empty in
      { t with children = CMap.add word.[i] (go (i + 1) child) t.children }
  in
  go 0 t
 
(* The node reached by following a prefix, if any. *)
let rec descend prefix i t =
  if i = String.length prefix then Some t
  else Option.bind (CMap.find_opt prefix.[i] t.children) (descend prefix (i + 1))
 
let mem word t = match descend word 0 t with Some n -> n.final | None -> false
 
(* Every key below a node, in lexicographic order. *)
let rec keys prefix t =
  (if t.final then [ prefix ] else [])
  @ List.concat_map (fun (c, child) -> keys (prefix ^ String.make 1 c) child) (CMap.bindings t.children)
 
let complete prefix t = match descend prefix 0 t with Some n -> keys prefix n | None -> []
let rec nodes t = 1 + CMap.fold (fun _ c acc -> acc + nodes c) t.children 0

mem "ten" true   mem "te" false   mem "tenor" false
complete "te"  tea team tease ted ten tent tenth
complete "in"  in inn
all keys, sorted: a i in inn tea team tease ted ten tent tenth to toast
after inserting "tee": 14 keys, the old trie still has 13
0..99999 as strings: 488890 characters in the keys, 100001 trie nodes

Completion finds the node for the prefix and lists the keys below it; because children are visited in character order, the keys come out sorted, so a trie also sorts its keys. The trie is persistent: inserting copies the nodes on the key's path and shares the rest, and the previous version remains valid. The keys 0 to 99999 contain 488,890 characters but need only 100,001 nodes, since every prefix of one of them, apart from the root, is another of them.

In a sparse trie, most nodes have one child, and long chains of them waste space. A radix tree, or compact trie, merges each such chain into a single edge labelled with a string, so that every internal node that is not a key has at least two children. A trie with $n$ keys then has at most $2n-1$ nodes, independent of the lengths of the keys. Morrison's PATRICIA stores in each node only the position of the next character, or bit, on which the keys below it differ, and skips the intervening characters without examining them; a lookup then compares the whole key once at the end^[3].

Integer keys

Reading an integer's bits as its characters, with an alphabet of two, gives a binary trie of depth at most the word size. Okasaki and Gill's Patricia trees for integers record at each branch the prefix shared by all keys below it and the first bit at which they differ^[5]:

(* Okasaki and Gill's little-endian Patricia tree for integer keys. A
   branch records the bits shared by all keys below it (the prefix) and the
   first bit where they differ (the branching bit). *)
type 'a t = Empty | Leaf of int * 'a | Branch of int * int * 'a t * 'a t
 
let zero_bit k m = k land m = 0
let mask k m = k land (m - 1)
let match_prefix k p m = mask k m = p
let lowest_bit x = x land -x
 
let join p0 t0 p1 t1 =
  let m = lowest_bit (p0 lxor p1) in
  if zero_bit p0 m then Branch (mask p0 m, m, t0, t1) else Branch (mask p0 m, m, t1, t0)
 
let rec insert k v = function
  | Empty -> Leaf (k, v)
  | Leaf (j, _) as t -> if j = k then Leaf (k, v) else join k (Leaf (k, v)) j t
  | Branch (p, m, t0, t1) as t ->
      if match_prefix k p m then
        if zero_bit k m then Branch (p, m, insert k v t0, t1) else Branch (p, m, t0, insert k v t1)
      else join k (Leaf (k, v)) p t
 
let rec find k = function
  | Empty -> None
  | Leaf (j, v) -> if j = k then Some v else None
  | Branch (_, m, t0, t1) -> find k (if zero_bit k m then t0 else t1)
 
let rec depth = function Empty | Leaf _ -> 0 | Branch (_, _, a, b) -> 1 + max (depth a) (depth b)

all 100000 keys found with the right value: true
depth 21 (keys have 30 bits)
same keys, different order, identical trees: true

A trie's shape depends only on the set of keys, never on the order in which they were inserted, unlike a balanced search tree, whose shape depends on its history. Two Patricia trees holding the same keys are structurally equal, which makes equality tests fast, and union and intersection can be computed by merging the two trees in one pass, which is why Okasaki and Gill called them mergeable. Haskell's Data.IntMap and the ptmap and ptset libraries for OCaml are Patricia trees.

A ternary search tree stores each node's children as a binary search tree over characters, which uses less memory than an array of children and is competitive with hashing for string keys^[10]. The adaptive radix tree changes the representation of each node with its number of children, among arrays of 4, 16, 48 and 256 entries, and is used as an index in main-memory databases^[7]. A hash array mapped trie, or HAMT, is a trie over the bits of the keys' hash values, which gives persistent hash maps^[6]. A suffix tree is the compressed trie of all suffixes of a text, and answers substring queries in time proportional to the length of the pattern^[11]. Hinze generalized tries from strings to keys of any algebraic data type, with the shape of the trie derived from the shape of the key type^[12].

Autocompletion and spelling correction use a trie of words, since the words sharing a prefix are one subtree. The Aho–Corasick algorithm adds failure links to a trie of patterns and finds all occurrences of all patterns in a text in one pass^[8], and it is the basis of tools such as fgrep. Internet routers choose a route by the longest prefix of the destination address present in the routing table, which is a lookup in a binary trie of address prefixes; level-compressed tries make it fast enough for line-rate forwarding^[9].

De la Briandais described searching files with variable-length keys stored in a tree of characters in 1959^[1], and Fredkin named the structure the trie in 1960^[2]. Morrison introduced PATRICIA in 1968^[3], and Knuth analysed digital searching in the third volume of The Art of Computer Programming^[4]. Okasaki and Gill brought Patricia trees to functional programming as mergeable integer maps in 1998^[5], and Bagwell's hash array mapped tries of 2001 made tries the standard structure for persistent hash maps^[6].

• Hash array mapped trieA hash array mapped trie (HAMT) is a trie over the bits of the keys' hash values: each level consumes a few bits, usually five, to choose one of 32 children, and each node stores only its occupied children in a compact array, located by counting bits in a 32-bit bitmap. Lookups follow about log32 n levels. Updated by copying the path to the changed leaf, a HAMT is a persistent hash map with small, cache-friendly nodes, and it is the standard implementation of immutable maps and sets in Clojure, Scala and Haskell's unordered-containers.
• RopeA rope is a binary tree whose leaves are strings and whose internal nodes represent the concatenation of their children, with each node caching the length of its left subtree. Concatenation creates one node instead of copying, and indexing, splitting, insertion and deletion in the middle take time logarithmic in the length for a balanced rope. Ropes are immutable and share structure between versions, which makes them suited to text editors with undo and to programs that build long strings piece by piece.
• Red-black treeA red-black tree is a binary search tree whose nodes are coloured red or black so that no red node has a red child and every path from the root to a leaf passes through the same number of black nodes. The two rules keep the height at most 2 log2(n + 1), so search, insertion and deletion take O(log n) time. Red-black trees are an encoding of 2-3-4 trees as binary trees, and Okasaki's functional version reduces insertion to one rebalancing rule with four cases.
• Finger treeA persistent sequence with amortized constant-time access at both ends, and concatenation and splitting in logarithmic time. The ends are kept in buffers of one to four elements, and the middle is a finger tree of 2-3 nodes, one level deeper at each step down the spine.

1. [1]R. de la Briandais, “File searching using variable length keys”, Western Joint Computer Conference (1959).
2. [2]E. Fredkin, “Trie memory”, Communications of the ACM 3 (1960).
3. [3]D. R. Morrison, “PATRICIA—practical algorithm to retrieve information coded in alphanumeric”, Journal of the ACM 15 (1968).
4. [4]D. E. Knuth, The Art of Computer Programming, Vol. 3, §6.3 “Digital searching”, Addison-Wesley (2nd ed., 1998).
5. [5]C. Okasaki, A. Gill, “Fast mergeable integer maps”, Workshop on ML (1998).
6. [6]P. Bagwell, “Ideal hash trees”, Technical Report, EPFL (2001).
7. [7]V. Leis, A. Kemper, T. Neumann, “The adaptive radix tree: ARTful indexing for main-memory databases”, ICDE (2013).
8. [8]A. V. Aho, M. J. Corasick, “Efficient string matching: an aid to bibliographic search”, Communications of the ACM 18 (1975).
9. [9]S. Nilsson, G. Karlsson, “IP-address lookup using LC-tries”, IEEE Journal on Selected Areas in Communications 17 (1999).
10. [10]J. L. Bentley, R. Sedgewick, “Fast algorithms for sorting and searching strings”, SODA (1997).
11. [11]D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press (1997).
12. [12]R. Hinze, “Generalizing generalized tries”, Journal of Functional Programming 10 (2000).

last updated 27 September 2026