Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python trie: exact words, prefixes and node allocation

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

A trie indexes a key by storing its successive characters along a path, with a separate marker for a complete key.

Download Python source kit

Operation contract

The label index stores nonempty lowercase ASCII words of at most 32 characters. The endpoint marker distinguishes the stored label ledger from the prefix led. Duplicate insertion returns False rather than creating another label. Prefix lookup tests whether a path exists; exact lookup also requires the endpoint marker.

Failure and ownership boundary

The fixture permits at most 64 distinct labels and retains nodes for their shared prefixes. It does not support deletion, Unicode normalization or ranked suggestions. A prefix index for user display labels must first define a text policy rather than silently lowercasing every identifier. Python Unicode normalization: equality is not visual identity and Python dictionaries: insertion order and duplicate-key replacement describe those prior decisions.

Working program

python
class LabelTrie:
    def __init__(self):
        self.root = {}
        self.count = 0
    def checked(self, label):
        if type(label) is not str or not 1 <= len(label) <= 32 or any(not "a" <= character <= "z" for character in label):
            raise ValueError("lowercase ASCII label required")
    def insert(self, label):
        self.checked(label)
        if self.contains(label):
            return False
        if self.count == 64:
            raise ValueError("label budget")
        node = self.root
        for character in label:
            node = node.setdefault(character, {})
        node["$"] = True
        self.count += 1
        return True
    def lookup(self, label):
        self.checked(label)
        node = self.root
        for character in label:
            if character not in node:
                return None
            node = node[character]
        return node
    def contains(self, label):
        node = self.lookup(label)
        return node is not None and "$" in node
    def has_prefix(self, label):
        return self.lookup(label) is not None

labels = LabelTrie()
print(labels.insert("ledger"), labels.insert("ledger"))
print(labels.contains("led"), labels.has_prefix("led"))
print(labels.contains("ledger"))

Output

Output
True False
False True
True

Costs and limits

For a label of length L, traversal takes expected O(L) dictionary work. Allocated nodes are bounded by the total stored characters; Python dictionary/object overhead can dominate tiny labels.

Common Mistakes

  • A prefix path is not proof that the prefix itself was inserted.
  • Do not claim tries always use less memory than a hash set.

Connected lessons

Python dictionaries: insertion order and duplicate-key replacement, Python Unicode normalization: equality is not visual identity, Python prefix-function search: overlapping matches without rescanning.

Follow the related contract

Python trie deletion: remove one word without losing its prefix neighbors.

Check the next state boundary

Python compressed trie: merge single-child paths without losing terminal words.

python
trie-prefix
Storage details