Ternary Search Tree

ABSTRACT

A Ternary Search Tree is a hybrid data structure that combines the prefix-searching logic of a Multiway Trie with the space-efficient storage of a Binary Search Tree (BSTs). Each node stores a single character and has exactly three potential children: Left, Middle, and Right.

---

1. Structural Logic

In a TST, the relationship between a node and its children is determined by character comparisons and word progression:

• Left Child: Stores characters that are alphabetically smaller than the current node’s character.
• Right Child: Stores characters that are alphabetically larger than the current node’s character.
• Middle Child: Represents the next character in the current word string.
• Word Nodes: Nodes representing the end of a valid word are marked (e.g., colored blue).

---

2. Core Operations

Find

To search for a key, we compare the current character of the key with the current node’s label:

1. If Key Char < Node Label: Move to the Left child.
2. If Key Char > Node Label: Move to the Right child.
3. If Key Char == Node Label: * If this is the last character of the key, check if the node is a word-node.
   • Otherwise, move to the Middle child and move to the next character in the key.

find(key): // return True if key exists in this TST, otherwise return False
    node = root node of the TST
    letter = first letter of key
    loop infinitely:
        // left child
        if letter < node.label:
            if node has a left child:
                node = node.leftChild
            else:
                return False     // key cannot exist in this TST
 
        // right child
        else if letter > node.label:
            if node has a right child:
                node = node.rightChild
            else:
                return False     // key cannot exist in this TST
 
        // middle child
        else:
            if letter is the last letter of key and node is a word-node:
                return True      // we found key in this TST!
            else:
                if node has a middle child and letter is not the last letter of key:
                    node = node.middleChild
                    letter = next letter of key
                else:
                    return False // key cannot exist in this TST

Walk Through Example (Success)

Below is the same example from before, and we will step through the process of finding the word mid:

1. We start with node as the root node (‘c’) and letter as the first letter of mid (‘m’)
2. letter (‘m’) is greater than the label of node (‘c’), so set node to the right child of node (‘m’)
3. letter (‘m’) is equal to the label of node (‘m’), so set node to the middle child of node (‘e’) and set letter to the next letter of mid (‘i’)
4. letter (‘i’) is greater than the label of node (‘e’), so set node to the right child of node (‘i’)
5. letter (‘i’) is equal to the label of node (‘i’), so set node to the middle child of node (‘n’) and set letter to the next letter of mid (‘d’)
6. letter (‘d’) is less than the label of node (‘n’), so set node to the left child of node (‘d’)
7. letter (‘d’) is equal to the label of node (‘d’), letter is already on the last letter of mid (‘d’), and node is a “word node,” so success!

Walk Through Example (Fail)

Using the same example as before, let’s try finding the word cme, which might seem like it exists, but it actually doesn’t:

1. We start with node as the root node (‘c’) and letter as the first letter of cme (‘c’)
2. letter (‘c’) is equal to the label of node (‘c’), so set node to the middle child of node (‘a’) and set letter to the next letter of cme (‘m’)
3. letter (‘m’) is greater than the label of node (‘a’), but node does not have a right child, so we failed

Insert

To insert a key, compare the current character with the node’s label:

• If Key Char < Node Label: Move to the Left child. If null, create a new Left child and build a Middle-child “spine” for the remaining characters.
• If Key Char > Node Label: Move to the Right child. If null, create a new Right child and build a Middle-child “spine” for the remaining characters.
• If Key Char == Node Label: If last character: Mark current node as a word-node.
  • If not last character: Move to Middle child and next character. If Middle is null, build a “spine” of Middle children for the remaining characters.

insert(key): // insert key into this TST
    node = root node of the TST
    letter = first letter of key
 
    loop infinitely:
        // left child
        if letter < node.label:
            if node has a left child:
                node = node.leftChild
 
            else:
                node.leftChild = new node labeled by letter
                node = node.leftChild
 
                iterate letter over the remaining letters of key:
                    node.middleChild = new node labeled by letter
                    node = node.middleChild
 
                label node as a word-node
                break
 
        // right child
        else if letter > node.label:
            if node has a right child:
                node = node.rightChild
 
            else:
                node.rightChild = new node labeled by letter
                node = node.rightChild
 
                iterate letter over the remaining letters of key:
                    node.middleChild = new node labeled by letter
                    node = node.middleChild
 
                label node as a word-node
                break
 
        // middle child
        else:
            if letter is the last letter of key:
                label node as a word-node
                return true
 
            else:
                if node has a middle child:
                    node = node.middleChild
                    letter = next letter of key
                else:
                    iterate letter over the remaining letters of key:
                        node.middleChild = new node labeled by letter
                        node = node.middleChild
 
                    label node as a word-node
                    break

Walk Through Example

Below is the initial example of a Ternary Search Tree, and we will demonstrate the process of inserting the word cabs:

1. We start with node as the root node (‘c’) and letter as the first letter of cabs (‘c’)
2. letter (‘c’) is equal to the label of node (‘c’), so set node to the middle child of node (‘a’) and set letter to the next letter of cabs (‘a’)
3. letter (‘a’) is equal to the label of node (‘a’), so set node to the middle child of node (‘l’) and set letter to the next letter of cabs (‘b’)
4. letter (‘b’) is less than the label of node (‘l’), but node does not have a left child:
5. Create a new node as the left child of node, and label the new node with letter (‘b’)
6. Set node to the left child of node (‘b’) and set letter to the next letter of cabs (‘s’)
7. Create a new node as the middle child of node (‘s’), and label the new node with letter (‘s’)
8. Set node to the middle child of node (‘s’)
9. letter is already on the last letter of cabs, so label node as a “word node” and we’re done!

Remove

To remove a key, use the search logic to locate the target node:

• If search fails: The key does not exist; no action is taken.
• If search succeeds:
  • Navigate to the node representing the last character of the key.
  • Action: Unmark the word-node status (e.g., change the color from blue to white).

Note

To optimize memory, you could recursively delete nodes that no longer lead to any word-nodes, though simply unmarking is the standard logical removal.

remove(key): // remove key if it exists in this TST
    node = root node of the TST
    letter = first letter of key
    loop infinitely:
        // left child
        if letter < node.label:
            if node has a left child:
                node = node.leftChild
            else:
                return                               // key cannot exist in this TST
 
        // right child
        else if letter > node.label:
            if node has a right child:
                node = node.rightChild
            else:
                return                               // key cannot exist in this TST
 
        // middle child
        else:
            if letter is the last letter of key and node is a word-node:
                remove the word-node label from node // found key, so remove it from the TST
                return
            else:
                if node has a middle child:
                    node = node.middleChild
                    letter = next letter of key
                else:
                    return                           // key cannot exist in this TST

Walk Through Example

Below is the initial example of a Ternary Search Tree, and we will demonstrate the process of removing the word mid:

1. We start with node as the root node (‘c’) and letter as the first letter of mid (‘m’)
2. letter (‘m’) is greater than the label of node (‘c’), so set node to the right child of node (‘m’)
3. letter (‘m’) is equal to the label of node (‘m’), so set node to the middle child of node (‘e’) and set letter to the next letter of mid (‘i’)
4. letter (‘i’) is greater than the label of node (‘e’), so set node to the right child of node (‘i’)
5. letter (‘i’) is equal to the label of node (‘i’), so set node to the middle child of node (‘n’) and set letter to the next letter of mid (‘d’)
6. letter (‘d’) is less than the label of node (‘n’), so set node to the left child of node (‘d’)
7. letter (‘d’) is equal to the label of node (‘d’), letter is already on the last letter of mid, and node is a “word node,” so mid exists in the tree
8. Remove the “word node” label from node

---

3. Advanced Features

Like the Multiway Trie, the TST supports ordered operations and prefix-based utilities.

Alphabetical Iteration

Because TSTs maintain the BST property (Left < Node < Right), an In-Order Traversal can retrieve words in sorted order.

# Pseudocode for Ascending Order
ascendingInOrder(node):
    ascendingInOrder(node.leftChild)
    if node is a word-node:
        output word
    ascendingInOrder(node.middleChild)
    ascendingInOrder(node.rightChild)

Auto-complete

To find all words starting with a prefix:

1. Traverse the TST to the node representing the end of the prefix.
2. Perform an ascendingInOrder traversal on that node’s middle child subtree.

---

4. Evaluation for Lexicon ADT

The TST is often the preferred choice for implementing digital lexicons because it balances the trade-offs of other structures.

Feature	BST (AVL)	Multiway Trie	Ternary Search Tree
Search (Avg)	$O(\log n)$	$O(k)$	$O(k+\log n)$
Space Efficiency	High	Very Low	High
Alphabetical	Yes	Yes	Yes
Auto-complete	No	Yes	Yes

Key Takeaways

• Space over Speed: TSTs avoid the “wasted pointer” problem of Multiway Tries because each node only has 3 pointers instead of $|\Sigma |$ (e.g., 26 or 256).
• Balance Matters: Like a BST, a TST can become “skewed” (unbalanced) if words are inserted in a poor order. Shuffling words before insertion is a common optimization.
• The “Middle Ground”: It provides the prefix-matching power of a Trie with the memory footprint of a Tree.