Ternary Search Tree Operations
You'll learn how to implement search, insertion, and deletion in ternary search trees (TSTs) with support for prefix matching.
The Core Idea
A ternary search tree is a hybrid between a trie and a binary search tree. Each node has three children: left (for characters that come before), middle (for the next character in the word), and right (for characters that come after). This structure lets you perform string operations efficiently while using less memory than a standard trie.
Search Operation
To search for a word, compare the current character:
- If it's less than the node's character → go left
- If it's greater → go right
- If it matches → advance to the next character and go middle
You've found the word if you reach the end and the node is marked as a word-ending.
Insertion Operation
Insertion follows the same comparison logic as search. If a path doesn't exist, create new nodes as needed. When you insert the final character, mark that node as a complete word (often with a boolean flag).
Deletion Operation
Deletion is trickier: unmark the word-ending flag at the final node. If that node has no children and isn't part of another word, recursively remove nodes upward until you reach a node that's still needed (has other children or marks another word).
Prefix Matching
TSTs naturally support prefix queries. Traverse to the node representing the last character of the prefix using search logic, then collect all complete words in the subtree below that node's middle child.
Key Takeaway: TST operations combine character-by-character navigation (like tries) with three-way branching (left/middle/right), offering efficient search, insertion, deletion, and prefix matching with better space efficiency than standard tries.