Ternary Search Tree

A plain trie must choose how each node stores its children. A σ-wide array wastes slots on sparse branches. A Dictionary<char, Node> stores only real branches but hashes each character and loses the array’s natural order. A ternary search tree (TST) uses a small binary search tree keyed on the next character instead. Each node has three pointers, and character order survives.

Each node carries one split character and three links: lo for a smaller current character, hi for a larger one, and eq for an equal one. Only eq advances to the next character. A lookup moves sideways through lo or hi until the split matches, then moves one character deeper through eq. The key path is threaded through the eq links. lo and hi replace a trie’s child lookup with comparisons.

Compared with an array-backed trie, the TST reserves no slot for an absent symbol. It keeps lexicographic order and supports prefix or near-neighbour queries, but its per-position comparison trees can become unbalanced.

Core shape: trie positions linked by eq. At each position the alternatives form a BST split on the character via lo/hi → three pointers per node, not σ

VisualizationVisualizationComplexityComplexity

Visualization

Representation and Invariants

A node holds a split character, an end-of-key flag, and three child links:

• Split — the character this node discriminates on.
• Lo / Hi — subtrees for keys whose character at this same position sorts before / after Split. Following them does not consume a character.
• Eq — the subtree for the next position, taken only after the current character equals Split. Following it consumes one character.
• IsEnd — true when the eq-chain from the root to this node spells a complete stored key.

The key is never stored. cat is present when, starting at the root, three matched-then-eq steps land on a node whose Split is t and whose IsEnd is set. A single trie level — “which character comes next here?” — is exactly one BST reachable through lo/hi links, and the answer to that question is the eq link out of the matching node.

Three invariants hold:

1. BST order within a position. For any node, every Split in its Lo subtree is smaller and every Split in its Hi subtree is larger, both compared at the same string position. This is what makes an in-order walk of lo/eq/hi emit keys in sorted order.
2. Eq is the only depth-advancing link. The number of eq links from the root to a node equals that node’s character position. Lo and Hi stay at the current position; Eq moves forward exactly one.
3. IsEnd is independent of children. car and cart coexist: the node spelling car is flagged and still has an eq subtree carrying on to t.

The whole contract lives in the difference between “matched the split and there is more key” (follow eq) and “the character is smaller or larger” (follow lo/hi without advancing).

Complexity

TimeSpace

• Search hit (key length m): O(m + log n) avg, O(m + n) worst
• Search miss: O(m + log n) avg, O(m + n) worst
• Insert: O(m + log n) avg, O(m + n) worst
• Prefix collection: O(m + log n + k) avg, O(m + n + k) worst

n

number of keys stored in the tree

m

length of the inserted or queried key

k

total characters emitted by prefix collection

s

total characters across all stored keys

Where the Three-way Split Earns Its Place

The lo/eq/hi structure is not just a memory trick: it preserves character order while keeping fan-out fixed at three pointers per node.

• Sorted output for free. An in-order traversal — recurse lo, visit the eq subtree with Split appended, recurse hi — emits every key in lexicographic order without a separate sort. A Dictionary-backed trie has to collect and sort its children at each node to do the same.
• Near-neighbour and wildcard search. The comparison layout supports partial-match (.a.-style wildcards) and one-substitution spell-check queries: at a wildcard or an allowed-mismatch position, explore the alternative branches. Elsewhere, follow only the matching branch. A hash-map trie can perform the same search by iterating its actual children, so this is not an asymptotic TST advantage. Insertion and deletion edits need extra query-index state in either structure because they change which character positions align.
• Bounded fan-out. Three pointers per node means a TST is often smaller than a Dictionary<char, Node> trie after including the hash table’s own overhead per node, while avoiding the array trie’s σ reservation entirely.

Where it breaks is balance. Randomising insertion order gives only the expected average-case bound listed in the Complexity tab. It does not guarantee that bound. A deterministic log n term requires balancing the per-position BSTs. And like any prefix structure, a TST only pays off when keys share prefixes and have a meaningful character sequence. Opaque integer or float keys gain nothing from it.

Diagram and C# Implementation

TST holding cat, car, cup, bat

graph TD
  C["c"] -->|lo| B["b"]
  C -->|eq| A1["a"]
  A1 -->|eq| T1["t ✓ cat"]
  A1 -->|hi| U["u"]
  T1 -->|lo| R["r ✓ car"]
  U -->|eq| P["p ✓ cup"]
  B -->|eq| A2["a"]
  A2 -->|eq| T2["t ✓ bat"]

eq links (vertical) advance one character. lo/hi links stay at the same position and order the alternatives. car sits in the lo subtree of the t node because r < t at position 2. cup branches to hi at position 1 because u > a.

C# implementation

public sealed class TernarySearchTree
{
    private sealed class Node
    {
        public char Split;
        public Node? Lo, Eq, Hi;
        public bool IsEnd;
    }
 
    private Node? _root;
 
    public void Insert(string key)
    {
        if (!string.IsNullOrEmpty(key)) _root = Insert(_root, key, 0);
    }
 
    private static Node Insert(Node? node, string key, int d)
    {
        var c = key[d];
        node ??= new Node { Split = c };
 
        if (c < node.Split)          node.Lo = Insert(node.Lo, key, d);
        else if (c > node.Split)     node.Hi = Insert(node.Hi, key, d);
        else if (d < key.Length - 1) node.Eq = Insert(node.Eq, key, d + 1);
        else                         node.IsEnd = true;
 
        return node;
    }
 
    // Empty is never a stored key (Insert rejects it); the empty prefix matches everything.
    public bool Contains(string key) =>
        !string.IsNullOrEmpty(key) && Get(_root, key, 0) is { IsEnd: true };
 
    public bool StartsWith(string prefix) =>
        string.IsNullOrEmpty(prefix) || Get(_root, prefix, 0) is not null;
 
    private static Node? Get(Node? node, string key, int d)
    {
        if (node is null) return null;
        var c = key[d];
        if (c < node.Split)          return Get(node.Lo, key, d);
        if (c > node.Split)          return Get(node.Hi, key, d);
        if (d < key.Length - 1)      return Get(node.Eq, key, d + 1);
        return node;
    }
}

Only the else branch — a matched character with more key remaining — recurses on Eq and advances d. Contains and StartsWith share the same walk. Contains also demands the terminal node’s IsEnd flag.

Comparison

Every structure below stores a set of string keys. They differ in the per-node child representation and what that costs.

Structure	Character routing	Prefix / ordered support	Storage shape	Stronger case
Ternary search tree	Compares the next character through lo/eq/hi	Native prefix walk. In-order traversal is sorted	One character and three child pointers per node	Large or unknown alphabets with ordered output
Array-backed Trie	Indexes a fixed child slot	Native prefix walk. Symbol-order traversal is sorted	Reserves one child array at every node	Small fixed alphabets where direct indexing matters
Hash-map Trie	Hashes the next character	Native prefix walk. Sorting requires ordered child keys	Allocates only present children plus map overhead	Sparse large alphabets without TST shape sensitivity
Radix / PATRICIA trie	Compares substring-labelled edges	Native prefix walk. Sorted output requires symbol-ordered edges	Compresses single-child runs and stores edge labels	Long keys with many non-branching runs
Balanced Binary Search Tree	Compares complete keys	Ordered and range scans. Prefix search needs bounded key ranges	Stores one complete key per node	Total order over complete keys without shared-prefix structure

A radix trie wins when node count is the constraint and keys are long and sparse. A balanced BST keyed on whole strings is the choice when there are no shared prefixes to exploit and total order over complete keys is all that’s needed.

References

• Fast Algorithms for Sorting and Searching Strings
• TST.java (Princeton Algorithms)