Course contentsShow
← Computer Science
Lesson 637 of 2,87215. Tries and Specialized TreesFree lesson

Ternary Search Trees

Learn ternary search trees that combine trie efficiency with BST-like three-way branching at each node.

Ternary Search Trees

What you'll learn: You'll discover how ternary search trees blend the space efficiency of tries with the simpler branching structure of binary search trees.

What Makes Ternary Search Trees Different?

A ternary search tree (TST) is a hybrid data structure that stores strings efficiently by combining the best features of tries and binary search trees. Instead of having one child per possible character (like a standard trie), each node in a TST has exactly three children: left, middle, and right.

How Three-Way Branching Works

Each node stores a single character and makes a three-way decision:

  • Left child: stores strings where the current character is less than this node's character (alphabetically earlier)
  • Middle child: stores strings where the current character matches this node's character — this continues the same word
  • Right child: stores strings where the current character is greater than this node's character (alphabetically later)

Think of it like this: imagine you're spelling "CAT". At the first level, you find the node with 'C'. If the current node has a different letter, you go left (if alphabetically before 'C') or right (if after 'C'). When you find 'C', you go middle to continue spelling the word with 'A', then 'T'.

Why Use TSTs?

Ternary search trees save memory compared to standard tries. A trie might need 26+ child pointers per node (one per letter), but a TST always uses exactly three. Yet TSTs still maintain good search performance — comparable to tries for many operations.

The BST-like left-right branching keeps the structure balanced across different characters, while the middle links preserve the trie-like ability to share common prefixes.

Key Takeaway: Ternary search trees use three-way branching (left, middle, right) at each node to combine trie-like prefix sharing with BST-like space efficiency, offering a practical middle ground for string storage.