Marking Key Boundaries in a Trie

A trie stores keys by their characters, one node per character position. The structure has no natural notion of where a key ends: the node reached by spelling car is an ordinary internal node, indistinguishable from the one reached by spelling ca. Any trie that must answer exact membership questions therefore needs a separate signal at the node where a key terminates, and that signal has to be stored somewhere. The three candidate locations — a bit in the node header, a reserved child slot, and a pointer to a value — differ in what they cost and in what they let the structure do.

The bug that motivates the marker

Without a marker, the standard traversal test is wrong in a specific way. Searching for car walks c, a, r and finds a node. That node exists for every key with prefix car: cart, cargo, carpet. A search that reports success on reaching a node reports car as present whenever any longer key is present, which is a false positive for every prefix of every stored key. Deletion is worse: removing car must not remove the node if cart still needs it, and there is no information at the node to decide.

The fix is a boolean at each node recording whether some key ends exactly there. Once present, the marker separates three distinct node states: no key passes through, keys pass through, and a key ends here while others continue. Prefix queries depend on the first distinction, exact lookup on the second, and lexicographic enumeration on both.

A bit in the node header

The cheapest marker is a flag. Every node already has fields for its children; adding one bit to an existing word costs nothing at all if there is slack, and costs one byte if the layout is byte-aligned and the bit cannot be packed.

The trade is in how the flag interacts with the rest of the node. In a layout that stores a child count, a common convention is to encode the flag in the high bit of the count field, which keeps the node header a single machine word:

/* Node header: low 31 bits are the child count, bit 31 marks a key end. */
#define TERMINAL_BIT (1u << 31)
#define COUNT_MASK   (~TERMINAL_BIT)

typedef struct node {
    uint32_t header;
    struct node *child[];   /* flexible array: COUNT_MASK & header entries */
} node;

static inline int is_terminal(const node *n) {
    return (n->header & TERMINAL_BIT) != 0;
}

static inline uint32_t child_count(const node *n) {
    return n->header & COUNT_MASK;
}

Reading the flag is one mask; setting it is one OR. In a bitmap-plus-packed-children layout the flag can live in a separate word, or as one extra bit in the bitmap — but only if the alphabet leaves a label unused, which is the point of the next section. For alphabets that use all 256 byte values, no bit is spare.

The bit is sufficient for membership, prefix testing, and ordered enumeration. It is insufficient for anything that associates data with a key. A set can be represented this way; a map cannot, because the node has nowhere to hold the value. Adding a value pointer to every node doubles the per-node cost for the majority of nodes that do not hold a key, which in a natural-language dictionary is nearly all of them.

A reserved child slot

An alternative used by implementations that already have a dense child array is to reserve one label value as an end-of-key sentinel. In a byte trie, a node’s children array is indexed by 0–255, and one of those — commonly 0, the label that cannot appear inside a NUL-terminated C string — is repurposed. The child at that slot is either null or a pointer to the stored record.

This gives the map form for free: the sentinel slot holds the value pointer, so a key with an associated payload costs one child pointer and no extra structure. It also makes the traversal uniform: advancing to the next position is the same operation whether the byte is a real character or the terminator. In C, where keys arrive as NUL-terminated strings, the sentinel and the string terminator coincide, and a search loop that walks until the byte is zero lands on the sentinel slot by construction.

The cost is one child slot per node that cannot be used for a real character. Over a 256-way dense node that is 0.4 percent of the space, which is negligible. Over a four-way DNA node it is 25 percent, which is not. Over a compact representation where children are packed, a sentinel label consumes an entry in the packed array and shifts the rank arithmetic, so the bit flag is cheaper there. The sentinel also forecloses storing keys containing the sentinel byte — a real constraint for binary keys, where every byte value is legitimate.

Null-terminated keys and implicit boundaries

A third approach removes the marker entirely by making key boundaries part of the key encoding. If every key is stored with a terminator that cannot appear inside it, and the terminator is ordered below every real character, then the node reached by the terminator is the key-end node and nothing else needs recording.

This works well when the alphabet is small and closed. It fails when keys are arbitrary byte strings, because no byte is guaranteed absent. It also fails for a related reason: implicit boundaries make prefix queries ambiguous. A search for car stops at the node after r and cannot tell whether the key car is present or only cart, which is precisely the distinction the marker exists to supply.

The one place the terminator is an unambiguous boundary is a fixed-length key set, such as a hash table over 32-byte digests. Every key has the same length, so the depth of every key-end node is the same, and no marker is needed at all — depth equals key length is the test. This is why fixed-length radix structures over hashes and integers carry no terminal field, and why the marker question only arises for variable-length keys.

What the marker enables and what it costs

Once a marker exists, the three query classes separate cleanly.

Exact membership walks the key and tests the marker at the final node. Cost is the key length in node transitions plus one bit test: linear in the key length, which is the depth of the node reached rather than the number of keys.

Prefix enumeration walks the prefix and then performs a depth-first traversal of the subtree beneath it, emitting every terminal node it encounters. The traversal cost is proportional to the number of nodes in the subtree, which is bounded by the total length of the matching keys, not by the number of keys. This is why a trie answers “all keys starting with pre” in time proportional to the output rather than scanning the key set.

Longest-prefix matching walks the key and remembers the deepest terminal node seen. That single remembered position is the answer, and it costs one extra register during the walk — no backtracking, no second pass. Without a marker the walk would instead have to reconstruct which positions were legal key ends from the key set, which is the very information the marker stores. The technique underlies IP routing tables and is developed in multibit tries and longest-prefix matching, where a stored prefix length takes the marker’s place.

The cost of the marker is a small, constant per-node overhead, and it is paid on every node whether or not that node terminates a key. In a dictionary with a million keys of average length ten, the number of nodes is on the order of several million, while the number of terminal nodes is one million. Most nodes carry a false flag. A bit costs nothing to waste; a pointer costs eight bytes times several million, which is tens of megabytes of nulls.

Interaction with deletion

Deletion exposes the marker’s role in maintaining the structure. Removing a key clears the marker at its terminal node and then prunes upward: a node with no children and no marker is dead and can be freed, and the pruning continues while that condition holds. The condition is exactly “not terminal and no children”, so the marker participates in the pruning test, not just in lookup.

An implementation that stores a child count and a marker bit in one word can test both conditions with a single comparison against the count mask. An implementation that stores the marker in a sentinel child slot tests two separate fields. The difference is one branch per pruned level, which matters only in bulk deletion, but it is the kind of detail that determines whether deletion code is one loop or two.

There is a correctness trap worth naming: clearing a marker and freeing the node are separate steps, and a concurrent reader between them can observe the node after it has been unlinked. Tries are usually protected by a coarser lock or by being immutable, and the immutable case is where the marker design pays off most, since a marker bit can be set during construction and never changes afterwards.

Layout consequences

The marker’s placement is decided by the child representation, not independently of it. Bitmap nodes have slack in their presence word only for alphabets below the full 256 values; dense nodes have a free label for the sentinel; packed arrays prefer the header bit. The double-array layout described in child representation in tries has no header per state at all, so it encodes the marker either as a special transition on a reserved label or as a parallel bit vector indexed by state, the latter costing one bit per state and adding a single array access to the membership test.

In every case the marker is one bit of information per node. The design question is only where that bit lives and what else it is allowed to imply — a value pointer, a sentinel child, a legal character — and those implications are what distinguish a set from a map, a dense node from a compact one, and a mutable trie from a static one.