Level-order unary degree tries: encode child runs as bits

Last updated: 4 Oct 20269 min read

tutorial

A level-order unary degree sequence writes one bit for each outgoing edge of a node, followed by a zero that ends that node's child run. Nodes are visited breadth-first. Because edges are emitted in that order, the rank of a one bit identifies its child node number; the matching edge label sits at child number minus one. A previous zero marks where the current node's run begins, and the current zero marks where it ends. This lesson builds an ordinary temporary trie, emits the level-order arrays, then answers exact-word and prefix lookup using only those emitted arrays. It keeps explicit zero positions and one-rank prefixes for easy navigation. They are Python integer lists, so the model illustrates the encoding relation but is not a compact succinct implementation with packed bits and sampled rank/select directories.

Operational case

A static alert dictionary contains alert, alloy, bay, and badge. Exact lookup accepts alert, prefix lookup accepts al, and exact lookup rejects al because no terminal flag marks that prefix as a full key. The encoded tree has fifteen nodes, including the empty root. Children are emitted in sorted label order, so a lookup can stop scanning a child run once it passes the requested character. An empty string may still be a valid exact key if it was included during construction; its terminal flag belongs to the root. After construction, adding a term would require rebuilding the level-order layout and its rank/zero helpers.

Working Python program

class AlertTrieNode:
    def __init__(self):
        self.children = {}
        self.terminal = False


class LevelOrderAlertTrie:
    def __init__(self, terms):
        root = AlertTrieNode()
        for term in terms:
            node = root
            for character in term:
                node = node.children.setdefault(character, AlertTrieNode())
            node.terminal = True
        self.degree_bits = []
        self.edge_labels = []
        self.terminal = []
        self.zero_positions = []
        self.rank_ones = []
        queue = [root]
        cursor = 0
        ones = 0
        while cursor < len(queue):
            node = queue[cursor]
            cursor += 1
            self.terminal.append(node.terminal)
            for label, child in sorted(node.children.items()):
                self.degree_bits.append(1)
                ones += 1
                self.rank_ones.append(ones)
                self.edge_labels.append(label)
                queue.append(child)
            self.degree_bits.append(0)
            self.rank_ones.append(ones)
            self.zero_positions.append(len(self.degree_bits) - 1)

    def _follow(self, prefix):
        node_id = 0
        for character in prefix:
            start = self.zero_positions[node_id - 1] + 1 if node_id else 0
            end = self.zero_positions[node_id]
            child_id = None
            for position in range(start, end):
                candidate = self.rank_ones[position]
                label = self.edge_labels[candidate - 1]
                if label == character:
                    child_id = candidate
                    break
                if label > character:
                    break
            if child_id is None:
                return None
            node_id = child_id
        return node_id

    def contains(self, term):
        node_id = self._follow(term)
        return node_id is not None and self.terminal[node_id]

    def has_prefix(self, prefix):
        return self._follow(prefix) is not None


terms = LevelOrderAlertTrie(["alert", "alloy", "bay", "badge"])
print("alert=", terms.contains("alert"), " al-prefix=", terms.has_prefix("al"),
      " al-key=", terms.contains("al"), " nodes=", len(terms.terminal), sep="")

Output

alert=True al-prefix=True al-key=False nodes=15

Time, space, and tradeoff

Building a temporary trie takes O(M) character visits for M total input characters, plus child-label sorting at each node before encoding. The emitted degree sequence has 2V - 1 bits for V nodes, with V - 1 edge labels and V terminal flags. This Python example also stores O(V) integer references for zero positions and rank prefixes, so those counts describe a conceptual layout rather than actual packed memory. Lookup visits one child run per character and costs O(sum of visited node degrees); with a fixed bounded alphabet it is O(P) for prefix length P, but a wide branching node can add scan work. It supports static exact and prefix existence only, not updates or autocomplete ranking.

Common Mistakes

Do not omit terminal flags for keys that end at internal trie nodes.
Do not treat the root as an edge label.
Do not call unpacked Python arrays a measured succinct index.
Do not mutate the temporary trie after emitting a static level-order layout.

Connected lessons

Compare its storage and lookup contract with Elias–Fano: split sorted IDs into low parts and high bits, Chunked integer sets: switch sparse arrays to dense bitmaps, Gap-encoded postings: add checkpoints to bytewise seeks, then run the index audit and contract quiz.

Ternary search trees: branch by character and continue prefixes adds a keyed lookup comparison.

Balanced-parentheses trees: encode an ordered hierarchy adds a distinct structure contract to compare.

data structures

trees-and-heaps