Skip to content
Tutorials Center
My learning

Topics

Lesson 102 of 225 ยท Trees

Ternary Search Trees

Learn the ternary search tree: a trie that stores one character per node with three links. Insert, search, delete and autocomplete in Python, and compare it with a trie.

A trie is wonderful for words and prefixes, but each node usually carries a whole table of children: a 26-slot array or a dictionary. Most of those slots stay empty. A ternary search tree (TST) keeps the trie idea of "one character per level" and cuts the memory by giving every node just three links instead of a table.

Think of it as a trie and a binary search tree fused together. Within one character position, the nodes form a small binary search tree ordered by character. Moving to the next character in the word means taking a separate "middle" link. This lesson builds one from scratch, adds autocomplete, handles deletion, and compares it with a trie.

Each node holds one character ch, a flag is_end that says "a word finishes here", and three children:

  • lo: the subtree of characters smaller than ch at the same position.
  • eq: the next position of the word, reached when the current character matches.
  • hi: the subtree of characters larger than ch at the same position.

So lo and hi behave like the left and right links of a binary search tree, while eq is the "go to the next letter" link of a trie. The words cat, cap, bat and up form this picture:

graph TD
    c["c"] -->|lo| b["b"]
    c -->|eq| a1["a"]
    c -->|hi| u["u"]
    b -->|eq| a2["a"]
    a2 -->|eq| t2["t (end)"]
    a1 -->|eq| p["p (end)"]
    p -->|hi| t1["t (end)"]
    u -->|eq| p2["p (end)"]

Missing children are not drawn. cap and cat share the path c, a, then p and t sit side by side at the third position.

Searching for cat: at the root c the first letter matches, so follow eq to a; it matches, follow eq to p; t is larger than p, so follow hi to t; the word is finished and is_end is true.

The loop is the same for both: look at the current character of the word and the current node's character.

  • If the word character is smaller, go lo; larger, go hi.
  • If equal and the word has more characters, go eq and move to the next character; if it was the last character, this is where the word ends.

Insert creates a node whenever the link it wants to follow is missing. Search stops with "not found" when it falls off the tree, or when it reaches the last character on a node whose is_end is false (the word is only a prefix of something longer).

Python A ternary search tree: insert and search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

ca and u are only prefixes: the walk succeeds, but is_end is false, so contains says False. That distinction is exactly why the flag exists.

Autocomplete

To list every word that starts with a prefix, first walk to the node where the prefix's last character matches. Every word with that prefix lives below that node's eq link (plus the node itself, if the prefix is a whole word). Then collect the words with an in-order walk: visit lo, then the node itself (and its eq subtree), then hi. That gives the words in alphabetical order for free.

Python Prefix search in alphabetical order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the result for t is already sorted without any call to sorted.

Deleting a word

The simplest delete clears the is_end flag, which leaves the nodes behind. That is fine for most uses, and fast: one search plus one assignment. If you want to reclaim memory, remove nodes on the way back up that have no children and are not word ends. Because a node may still be reachable through lo or hi from a neighbor, you can only drop a node when all three links are empty and it does not end another word.

Python Delete with pruning

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The count stays at 6 after the first two deletes. Deleting card keeps the d node, because the e of care hangs off its hi link; deleting car keeps r, because care still continues below it. Pruning happens only once a node has nothing below and ends no word, so the last two deletes collapse everything at once.

TST or trie?

Trie (dict per node) Ternary search tree
Space A table of children per node Three pointers per node
Search time O(L), L = word length O(L + log n) comparisons in a balanced shape
Prefix search Direct Direct, results in sorted order
Wide alphabets (Unicode) Big tables or dictionaries No table, handles any comparable symbol
Shape depends on Only the set of words The insertion order (like a plain BST)

A TST can degenerate: inserting words in sorted order makes each character's little tree a chain, so lookups cost more comparisons. A common fix is to insert the words in a shuffled order, or to start from the median word. For plain exact lookup a hash table is usually faster, but a TST wins when you need prefix queries, sorted output, or "near" matches (for example, all words that match t?e where ? is a wildcard) with a small memory footprint.

Common mistakes

  • Treating a successful walk as a hit. Always check is_end at the last character.
  • Following eq when the character mismatches. eq is taken only on a match, lo and hi handle mismatches.
  • Pruning a node that still has a lo or hi neighbor. Those belong to other words.
  • Forgetting the empty string. Our TST rejects it, because a node needs at least one character.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a ternary search tree, when do you follow the middle (eq) link?

    Smaller and larger characters use the lo and hi links, which are like a binary search tree at one position. A match advances to the next character through eq.
  2. 2. Searching for 'ca' succeeds in walking the tree, but contains('ca') is False. Why?

    Reaching the last character is not enough. The word exists only if some inserted word finished exactly at that node.
  3. 3. Which words come out first when you collect the words under a prefix?

    Visiting lo, then the node and its eq subtree, then hi, is an in-order walk, so words appear in alphabetical order without sorting.
  4. 4. What is the main weakness of a ternary search tree compared with a trie?

    Each position is a plain binary search tree, so sorted insertions create long chains. Shuffling the words or inserting medians first avoids this.

Summary

  • A ternary search tree stores one character per node with three links: lo, eq and hi.
  • lo and hi act like a binary search tree among characters at one position; eq moves to the next character.
  • Search and insert cost O(L + log n)-ish comparisons for a word of length L, and need the is_end flag to tell words from prefixes.
  • Prefix queries and alphabetical listing fall out of an in-order walk.
  • Delete by clearing is_end, and prune nodes only when all three links are empty and the node ends no word.
  • It uses less memory than a table-based trie but depends on insertion order.

Next: Scapegoat Trees and Self-Organizing Lists