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

Ternary search trees: branch by character and continue prefixes

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A ternary search tree stores one character in each node. A smaller character follows the left link without consuming the query position; a larger character follows the right link. An equal character consumes one position and follows the equal link. A terminal flag distinguishes a complete term from a prefix that merely leads to longer terms. This implementation also tracks the empty term explicitly because it has no character node. Its completion walk visits left, current, equal, then right branches, yielding lexicographic order under Python string comparison. Unlike a flat hash set, the structure exposes shared prefixes for enumeration. It is not balanced, so insertion order can create long left or right chains and a poor worst-case lookup.

Operational case

The incident vocabulary contains alarm, alert, alpine, valve, and al. Requesting completions for al returns the shorter complete term first, followed by alarm, alert, and alpine. Asking whether alp is an exact term returns false even though it reaches a valid prefix path. Inserting an existing term again leaves a single terminal flag; it does not add a duplicate answer. A completion for an absent prefix returns an empty list. A full enumeration visits all stored character nodes, while a narrow prefix enumeration avoids branches before the matching prefix but still walks the entire matching subtree.

Working Python program

python
class TermNode:
    def __init__(self, character):
        self.character = character
        self.left = None
        self.equal = None
        self.right = None
        self.terminal = False


class IncidentTermIndex:
    def __init__(self):
        self.root = None
        self.empty_term = False

    def insert(self, term):
        if not isinstance(term, str):
            raise TypeError("term must be text")
        if not term:
            self.empty_term = True
            return

        def place(node, offset):
            character = term[offset]
            if node is None:
                node = TermNode(character)
            if character < node.character:
                node.left = place(node.left, offset)
            elif character > node.character:
                node.right = place(node.right, offset)
            elif offset + 1 == len(term):
                node.terminal = True
            else:
                node.equal = place(node.equal, offset + 1)
            return node

        self.root = place(self.root, 0)

    def _terminal_node(self, term):
        node = self.root
        offset = 0
        while node is not None:
            character = term[offset]
            if character < node.character:
                node = node.left
            elif character > node.character:
                node = node.right
            elif offset + 1 == len(term):
                return node
            else:
                offset += 1
                node = node.equal
        return None

    def contains(self, term):
        if not term:
            return self.empty_term
        node = self._terminal_node(term)
        return node is not None and node.terminal

    def complete(self, prefix):
        if not prefix:
            base = self.root
            results = [""] if self.empty_term else []
        else:
            terminal = self._terminal_node(prefix)
            if terminal is None:
                return []
            results = [prefix] if terminal.terminal else []
            base = terminal.equal

        def collect(node, stem):
            if node is None:
                return
            collect(node.left, stem)
            word = stem + node.character
            if node.terminal:
                results.append(word)
            collect(node.equal, word)
            collect(node.right, stem)

        collect(base, prefix)
        return results


terms = IncidentTermIndex()
for label in ("alarm", "alert", "alpine", "valve", "al"):
    terms.insert(label)
print("al=", terms.complete("al"), " exact=", terms.contains("alp"), sep="")

Output

Output
al=['al', 'alarm', 'alert', 'alpine'] exact=False

Time, space, and tradeoff

Let P be prefix length, H the number of comparison nodes examined while finding it, and M the number of character nodes below it. Exact lookup costs O(H), which can approach O(N) for N stored characters in an unbalanced tree. Completion costs O(H + M + output characters) because results are materialized as new strings. Storage is O(N) nodes and pointers. Recursive insertion and enumeration also use O(tree height) call-stack space and can hit Python recursion limits on a deliberately skewed vocabulary. A balanced sibling-search scheme could improve comparisons, but this program keeps the node invariant visible.

Common Mistakes

  • Do not follow an equal link after a smaller or larger comparison.
  • Do not accept a prefix as a complete term without its terminal flag.
  • Do not promise logarithmic lookup from an unbalanced sibling search tree.
  • Do not omit the empty term when the API allows it.

Connected lessons

Compare lookup and update behavior with Bitmap hash tries: copy paths for immutable alert maps, Binary radix routing: choose the longest matching prefix, Extendible hashing: split buckets through a shared directory, then run the index audit and contract quiz.

BK-trees: search incident labels within edit distance adds a distinct structure contract to compare.

data structures
trees-and-heaps
Storage details