Implementing a ternary search tree for efficient string search

A ternary search tree (TST) is a specialised data structure for storing and searching strings. It combines the character-by-character navigation of a trie with the smaller branching factor of a binary search tree. Each node stores one character and has three possible links: left, equal, and right. Learn more about Understanding The Expectation Maximization Algorithm.

This design is useful when an application needs exact word lookup, prefix matching, autocomplete, or a dictionary of many strings. Compared with a traditional trie, a TST can use less memory because it does not need a large array of child pointers for every possible character.

A TST is particularly attractive for text-heavy software. Search boxes, command interpreters, spell checkers, contact lists, and indexing tools can all benefit from quickly finding words that share a prefix. It also provides a practical exercise in recursion, tree invariants, and complexity analysis.

The implementation below uses Python, although the same structure can be written in C or another language. The examples focus on clarity first, then examine balancing, duplicate handling, prefix queries, and production concerns such as Unicode and memory usage.

How a ternary search tree stores words

Each TST node contains four important fields:

• char: the character held by the node
• left: characters smaller than char at the same word position
• equal: the next character in a word
• right: characters larger than char at the same word position
• is_end: whether a complete word ends at this node

Consider the words cat, car, and dog. The root might contain c. The equal link from c leads to a, and the next character is selected through the equal link again. At the final character, is_end marks a complete stored word. A word such as can shares the first two nodes before branching through a left or right link at the third position.

The three-way structure has a precise meaning. A node's left subtree contains another character at the same position that sorts before the node's character. Its right subtree contains a character that sorts after it. The equal subtree represents the next position in the string. This differs from an ordinary binary search tree because comparisons happen within a character position, while the equal link advances through the word.

A TST does not need a separate node for every possible alphabet character. That can be valuable for a large character set, including accented letters and symbols. It also makes the structure more compact than a fixed-array trie in many workloads, although the actual memory benefit depends on node allocation overhead and the number of shared prefixes.

Building the core Python implementation

The node and insertion operation can be implemented with a small recursive class. An empty input is ignored in this version, so the tree stores non-empty strings only.

class Node:
    def __init__(self, char):
        self.char = char
        self.left = None
        self.equal = None
        self.right = None
        self.is_end = False


class TernarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, word):
        if not word:
            return
        self.root = self._insert(self.root, word, 0)

    def _insert(self, node, word, index):
        char = word[index]

        if node is None:
            node = Node(char)

        if char < node.char:
            node.left = self._insert(node.left, word, index)
        elif char > node.char:
            node.right = self._insert(node.right, word, index)
        elif index + 1 < len(word):
            node.equal = self._insert(node.equal, word, index + 1)
        else:
            node.is_end = True

        return node

The recursion has two distinct movements. A left or right movement keeps the same index, because the algorithm is still looking for a suitable node at the current character position. An equal movement increments index, because the current character matched and the next character must be stored.

This distinction is the most common source of implementation errors. Incrementing the index while moving left or right skips a character position; failing to increment it on an equal move can cause infinite recursion. Marking is_end rather than adding a special terminator also allows one word to be a prefix of another, such as car and cart.

For a broader collection of algorithms and programming examples, the web development guide provides useful surrounding context about how data structures can support interactive applications. A search field in a web application might use a TST-backed service to retrieve suggestions as a user types.

Exact lookup and prefix matching

Exact lookup follows the same comparison rules as insertion. When the current character is smaller or larger than the node character, traversal moves left or right without advancing through the word. A matching character advances through the equal link. The word exists only if the final node has is_end set to True.

    def contains(self, word):
        if not word:
            return False

        node = self.root
        index = 0

        while node is not None:
            char = word[index]

            if char < node.char:
                node = node.left
            elif char > node.char:
                node = node.right
            elif index + 1 == len(word):
                return node.is_end
            else:
                index += 1
                node = node.equal

        return False

Prefix search needs one extra operation: locate the node representing the last character of the prefix, then traverse its equal subtree to collect all completed words below it. If the prefix node itself is terminal, the prefix is also a valid result.

    def starts_with(self, prefix):
        if not prefix:
            return []

        node = self.root
        index = 0

        while node is not None:
            char = prefix[index]

            if char < node.char:
                node = node.left
            elif char > node.char:
                node = node.right
            elif index + 1 < len(prefix):
                index += 1
                node = node.equal
            else:
                results = []
                if node.is_end:
                    results.append(prefix)
                self._collect(node.equal, prefix, results)
                return results

        return []

    def _collect(self, node, text, results):
        if node is None:
            return

        self._collect(node.left, text, results)

        current = text + node.char
        if node.is_end:
            results.append(current)

        self._collect(node.equal, current, results)
        self._collect(node.right, text, results)

The collection method performs an in-order traversal of left and right branches, so results are returned in lexicographic order when character comparison follows the desired ordering. It is suitable for autocomplete, although a real interface should usually cap the number of returned suggestions to avoid doing unnecessary work.

For example, a Brisbane retailer might use prefixes from product names, while a Sydney transport application could search station names. Prefix matching is also useful for Australian postcodes or suburbs, but input normalisation should be defined carefully because spelling, capitalisation, and punctuation affect the tree.

Complexity, shape, and memory behaviour

Let m be the length of the searched string. In a well-shaped TST with a fixed alphabet, an exact search is commonly described as approximately O(m), because each character is processed once and the character comparisons remain limited. A more precise analysis includes the height of the left and right search trees at each character position.

If insertion occurs in sorted order, the same-level binary search trees can become highly skewed. In that case, searching for a character may require many comparisons before reaching the equal link. The worst-case cost can approach O(m²) for a long string, although practical behaviour depends on the input distribution and alphabet. Randomised insertion, bulk construction, or explicit rebalancing can improve the shape.

Prefix enumeration adds the cost of visiting the matching subtree. If k characters are in the prefix and r results are returned, the work is roughly the cost of locating the prefix plus the nodes needed to produce those results. No index can avoid the cost of outputting a large result set, so pagination or a result limit is useful.

A TST usually uses less structural space than a trie with a full child array. Its storage is approximately proportional to the number of distinct character positions in the stored words, plus one node per allocated character. Shared prefixes reduce duplication. Python object overhead can still be substantial, so a C implementation may be preferable for a very large dictionary or latency-sensitive service.

Making the tree reliable in real applications

Text processing requires decisions beyond the tree itself. Should searches be case-sensitive? Should café and cafe be treated as different terms? Should hyphens, apostrophes, and whitespace be retained? A normalisation function can convert text to lowercase, apply Unicode normalisation, and remove or preserve punctuation according to the application's requirements.

Duplicate insertion is harmless in the implementation because is_end is a Boolean. If the application needs frequencies, scores, definitions, or document identifiers, the node can store an associated value or a list of values. Autocomplete systems often attach popularity scores and rank the collected results rather than returning pure alphabetical order.

A TST can also be adapted for deletion. The algorithm first clears is_end at the final node, then removes nodes that have no left, equal, or right children and are not terminal. Care is needed when a node is shared by several words: deleting car must not damage cart or care.

Testing should include empty input, a missing root, words that share prefixes, words where one is a prefix of another, repeated insertion, case variations, and characters outside basic ASCII. Property-based tests can compare contains and starts_with against a Python set and a sorted list. For ideas about systematic iteration over combinations and test cases, Python itertools techniques can help generate representative inputs.

Choosing a suitable use case

A TST is a strong choice when the workload contains many strings with shared prefixes and requires both exact lookup and prefix queries. It is less compelling when the application only needs membership checks, where a hash set is usually simpler and offers expected constant-time lookup. A sorted array with binary search may also be more memory-efficient for a static dictionary, especially when prefix queries are infrequent.

For an Australian application, privacy and data governance deserve attention. A contact-search feature storing names, phone numbers, or addresses may handle personal information covered by the Privacy Act 1988 and the Australian Privacy Principles. The tree should contain only the data required for the feature, with access controls and retention rules applied outside the data structure.

The local market also influences design. A Melbourne job board may need case-insensitive matching for employer names, while a regional service may need to search Indigenous place names, accented words, and multiple spellings. Australian English conventions, suburb names, and the everyday use of mobile search all make normalisation and ranking decisions visible to users.

A practical decision process is:

• Use a TST when prefix completion and exact lookup are both central requirements.
• Normalise input consistently before insertion and searching.
• Limit autocomplete results and attach ranking data when alphabetical order is insufficient.
• Measure memory and latency with the real dictionary, including Australian names and place terms.
• Consider a trie, sorted array, database index, or hash set when the workload does not need TST features.
• Add privacy controls when stored strings can identify people or reveal sensitive information.

A working TST is therefore more than three pointers and a recursive function. Its effectiveness comes from preserving the character-position invariant, selecting suitable input normalisation, testing irregular cases, and matching the structure to the search workload. When those decisions align, it offers a compact and understandable foundation for string indexing and autocomplete.