Ternary Search Tree Search

Ternary search tree search stores strings in a tree where each node contains one character and has three children.

The left child stores smaller characters, the middle child continues the current string, and the right child stores larger characters. This combines properties of binary search trees and tries.

Problem

Given a ternary search tree root root and a string key s, determine whether s is stored as a complete key.

Return true if present, otherwise false.

Structure

Each node stores:

field	meaning
`char`	character stored at this node
`left`	next node for smaller character
`mid`	next node for equal character and next string position
`right`	next node for larger character
`is_terminal`	marks the end of a stored key

Algorithm

Compare the current query character with the node character.

ternary_search_tree_search(root, s):
    if s is empty:
        return false

    node = root
    i = 0

    while node != null:
        c = s[i]

        if c < node.char:
            node = node.left

        else if c > node.char:
            node = node.right

        else:
            if i == length(s) - 1:
                return node.is_terminal

            i = i + 1
            node = node.mid

    return false

Example

Stored keys:

key
“cat”
“car”
“dog”

One possible ternary search tree:

A clearer search path for "car" is:

step	query char	node char	action
1	c	c	equal, go middle
2	a	a	equal, go middle
3	r	t	r < t, go left
4	r	r	equal, terminal true

The * marks a terminal node.

Correctness

At each node, the current query character is compared with the node character. If it is smaller, only the left subtree can contain a matching continuation. If it is larger, only the right subtree can contain it. If it is equal, the search advances to the next character through the middle child.

This exactly mirrors lexicographic search over strings. When the last character is matched, the terminal flag determines whether the full string, rather than only a prefix, is stored.

Therefore the algorithm returns true exactly when the key exists in the ternary search tree.

Complexity

Let $L$ be the string length and $h_c$ be the height of character comparison trees at each level.

case	time
balanced character branches	$O(L \log \sigma)$
typical sparse strings	close to $O(L)$
worst case	$O(L + n)$

Here $\sigma$ is the alphabet size.

Space complexity for iterative search is:

O(1)

When to Use

Ternary search trees are useful when:

keys are strings
memory use should be lower than a full array based trie
prefix search is needed
ordered traversal is useful

Compared to ordinary tries, ternary search trees avoid storing a large child array per node. Compared to hash tables, they preserve prefix and lexicographic operations.

Implementation

class TSTNode:
    def __init__(self, char):
        self.char = char
        self.left = None
        self.mid = None
        self.right = None
        self.is_terminal = False

def ternary_search_tree_search(root, s):
    if not s:
        return False

    node = root
    i = 0

    while node is not None:
        c = s[i]

        if c < node.char:
            node = node.left
        elif c > node.char:
            node = node.right
        else:
            if i == len(s) - 1:
                return node.is_terminal

            i += 1
            node = node.mid

    return False

type TSTNode struct {
	Char       rune
	Left       *TSTNode
	Mid        *TSTNode
	Right      *TSTNode
	IsTerminal bool
}

func TernarySearchTreeSearch(root *TSTNode, s string) bool {
	runes := []rune(s)
	if len(runes) == 0 {
		return false
	}

	node := root
	i := 0

	for node != nil {
		c := runes[i]

		if c < node.Char {
			node = node.Left
		} else if c > node.Char {
			node = node.Right
		} else {
			if i == len(runes)-1 {
				return node.IsTerminal
			}

			i++
			node = node.Mid
		}
	}

	return false
}