Trie

A trie stores strings in a rooted tree whose edges represent symbols; the path from the root spells a prefix. A separate terminal marker distinguishes a stored word from a prefix of another. Storing to, tea and ten shares the initial t, and tea with ten also shares te. Lookup follows one edge per symbol, taking $O(m)$ time for a length-$m$ key when child selection is constant-time. Dense child arrays use more memory than sparse maps. A trie naturally supports prefix queries and longest-prefix matching.^[ref]

A trie terminal marker records that the path to a trie node is a complete stored key, independently of whether that node has children. Store to and top: the node after to must be terminal even though its p child continues to top. Testing only for leaf nodes would incorrectly report that to is absent.

Insertion sets the marker at the end of the key; membership requires both a matching path and a terminal marker. Deletion clears the marker and may prune nodes that have neither a marker nor children. The initial node can itself be terminal if the empty string is a stored key. A symbol outside the key alphabet can implement an explicit end marker instead, but it must be distinguished from ordinary key characters. These conventions separate exact-key lookup from prefix lookup and permit correct enumeration of keys that are prefixes of other keys.

Use backtracking through a dictionary trie, decrementing and restoring the available count for each traversed letter. Visit each letter-labelled child once when its count is positive, rather than choosing between indistinguishable occurrences. Every reachable complete word is then produced once, including words using only a subcollection of the original letter multiset.

A binary trie stores bit strings by following one edge for each bit, with child edges labeled zero and one. A chosen direction of traversal fixes whether low or high bits are read first.