A trie answers "does this word exist, and what
starts with this prefix" by spending one node per character, branching however many ways the
alphabet needs at each node — a full array slot per letter in the classic textbook version, or a
map sized to whatever's actually present, the way this site's own
trie page builds it. A
ternary search tree answers the exact same question a completely different way:
every node holds one character and exactly three pointers — left,
mid, right — turning the "which way to branch on this character" choice
into an ordinary binary search instead of an array or map lookup. Comparing the query's current
character against a node's own character sends the walk left (smaller), right (bigger), or — only
on an exact match — down into mid and on to the next character. A trie's
root is an empty sentinel that holds no character of its own; a TST has no such thing — the root
is itself a real character node, the first letter of whatever word got inserted first.
Loaded with the same eight words as the trie page, for a direct side-by-side: cat, car,
card, care, cop, do, dog, dot. Thick, dashed-style mid
edges mean "next character, exact match so far"; thin dotted edges mean "different
character, same position" — a left/right step never advances how much of
the query has matched. Insert adds a word, Search checks for an exact match, Prefix lists every
stored word starting with what you typed, and Delete removes a word and prunes whatever nodes it
can. Try Prefix with "ca", then Delete "cat" and watch what happens to every other word — see
Pitfalls before you're surprised by it.
mid. A node is created only when the recursion
runs off the tree entirely. After the last character matches, mark that node's
isEnd flag true.null), the word was never inserted. If the walk completes, the word is
stored only if the final node's isEnd is true — reaching the node isn't enough,
same subtlety as a trie (see Pitfalls).mid step past it), then
check whether that node itself is end-of-word or has a
mid child. Both checks matter, and skipping either one is wrong in a way that's
easy to miss (see Pitfalls) — reaching the node only proves something in the tree once compared
against this exact sequence of characters, not that anything continues it into a real word.isEnd flag if it was really stored, then unwind back up the recursion: a node can
be spliced out of its parent only once it has no left, no mid, no
right, and isn't itself end-of-word. Miss any one of those four checks and
a totally unrelated word that merely shares the node as a comparison branch point can vanish
along with it (see Pitfalls).class TSTNode {
constructor(ch) {
this.char = ch;
this.left = this.mid = this.right = null;
this.isEnd = false;
}
}
class TernarySearchTree {
#root = null;
insert(word) {
this.#root = this.#insertAt(this.#root, word, 0);
}
#insertAt(node, word, i) {
if (node === null) node = new TSTNode(word[i]);
if (word[i] < node.char) node.left = this.#insertAt(node.left, word, i);
else if (word[i] > node.char) node.right = this.#insertAt(node.right, word, i);
else if (i === word.length - 1) node.isEnd = true;
else node.mid = this.#insertAt(node.mid, word, i + 1);
return node;
}
search(word) {
let node = this.#root, i = 0;
while (node !== null) {
if (word[i] < node.char) node = node.left;
else if (word[i] > node.char) node = node.right;
else if (i === word.length - 1) return node.isEnd;
else { i++; node = node.mid; }
}
return false;
}
startsWith(prefix) {
const node = this.#prefixNode(prefix);
return node !== null && (node.isEnd || node.mid !== null);
}
#prefixNode(prefix) {
let node = this.#root, i = 0;
while (node !== null) {
if (prefix[i] < node.char) node = node.left;
else if (prefix[i] > node.char) node = node.right;
else if (i === prefix.length - 1) return node;
else { i++; node = node.mid; }
}
return null;
}
delete(word) {
if (!this.search(word)) return false;
this.#root = this.#deleteAt(this.#root, word, 0);
return true;
}
#deleteAt(node, word, i) {
if (node === null) return null;
if (word[i] < node.char) node.left = this.#deleteAt(node.left, word, i);
else if (word[i] > node.char) node.right = this.#deleteAt(node.right, word, i);
else if (i === word.length - 1) node.isEnd = false;
else node.mid = this.#deleteAt(node.mid, word, i + 1);
if (!node.isEnd && !node.left && !node.mid && !node.right) return null;
return node;
}
}The interactive demo's Prefix button extends startsWith the same way the trie
page's does: once #prefixNode lands on the prefix's own node, an in-order walk
(left, then the node itself, then mid, then right) collects
every complete word below it — and because left always holds smaller characters and
right always holds bigger ones at each level, that walk comes back
already lexicographically sorted, with no separate sort step. Verified from scratch against a
brute-force oracle (a plain JavaScript Set of words, checked by direct membership
and by linear-scanning for a prefix): 200 trials of 200 interleaved insert/search/startsWith/
prefix/delete operations each over a 2-letter alphabet forced into heavy branching (40,000
operations total), checking agreement after every single operation plus a full-vocabulary
sweep at the end of each trial, an exhaustive pass across all 32 subsets of a 5-word set (384
checks total), and a standing structural invariant checked after every operation across all
40,000 runs — no reachable node is ever left both non-word and childless. 0 mismatches, but only
after finding and fixing a real bug the first draft's startsWith had (see Pitfalls
below — it's the same bug written into the code above's corrected form). Separately measured: a
trie and a TST built over the same word list always end up with exactly the same number of
character nodes (12 either way for the 8-word demo set above; 2,071 either way for a 500-word
random sample) — the two structures never disagree on how many nodes a word list needs,
only on what each node costs to store (see Complexity). The real shipped
insertTST/searchTST/prefixTST/deleteTST
functions were extracted verbatim and re-run through an equivalent pass, plus a fake-DOM harness
driving the actual click handlers through a fixed sequence of operations against the preloaded
tree, confirming every log line and rendered match list. See /tmp/tst_verify.js and
/tmp/tst_page_verify.js, scratch, not committed.
A node being reachable via character comparisons doesn't mean the prefix it represents
has any completions at all. This is subtler than a trie's version of the same idea. In a
trie, every node reachable by walking a prefix is on that prefix's own path. In a TST,
walking a prefix can land on a node kept alive purely because a different, unrelated
word needs it as a left/right branch point at that exact character
position — the node exists, but nothing continues this prefix into a word. Checking
only "does the node exist" for startsWith is exactly the bug the first draft here
shipped with: verified concretely with 40,000 randomized operations, 29 of which disagreed with
the brute-force oracle before the fix, every one of them a false positive (reporting a prefix as
present when zero stored words actually start with it). The fix checks node.isEnd ||
node.mid !== null — either the node itself completes a word, or something continues past
it — not just whether the walk got that far.
Pruning on delete has to check all three children, not just the one the deleted word
actually walked through. A word's own deletion path only ever touches
mid links once it's past the first character that needed a left/
right step to arrive — but the node at that branch point can still be load-
bearing for a sibling word that shares nothing else with the word being deleted. Verified directly
on this page's own preloaded tree: implementing the prune check as !isEnd && !mid
(dropping left and right, an easy typo-shaped mistake given how similar
the three pointers look) and deleting "cat" wrongly deletes all seven other
words — car, card, care, cop,
do, dog, and dot all come back not-found afterward, despite
none of them sharing a single letter in common with "cat" beyond the root's own 'c'. The root
node's isEnd is false (no bare "c" was ever inserted) and, once "cat"'s own
mid chain is fully pruned, its mid pointer is null too — the buggy check
sees "not a word, no mid" and deletes the root itself, taking its entire
left subtree (everything starting with a letter before 'c' — every other word in the
demo) down with it. The correct four-way check keeps the root alive, since its left
pointer is still very much in use.
left/
right a small number of times instead of demanding an exact match, and the same
walk finds every stored word differing from the query by at most that many character
substitutions — a Hamming-distance-style near match a plain trie doesn't offer without extra
bookkeeping.< and > on whatever the keys are
made of, so it works unmodified over arbitrary comparable symbols — not just characters with an
obvious hash.Time: insert, search, and startsWith
are O(log σ + k) on average for a word or prefix of length k over an
alphabet of size σ — a trie's O(k) plus a logarithmic factor for the
per-node comparison, since finding the right branch at each character is now a binary search
instead of a single array or map lookup. That extra factor is usually much smaller than
log₂ σ suggests in practice: measured across 2,000 random 5-to-8-letter words
(12,992 characters, 26-letter alphabet), the shipped insert logic made 30,372 node comparisons
total — about 2.34 per character, well under log₂ 26 ≈ 4.70 — because the real
branching factor at any node is bounded by how many distinct characters actually diverge there,
not the full alphabet size, the same "only pay for what's used" idea a trie's map-based children
already lean on. Worst case degrades to O(σ + k), the same failure
mode as an unbalanced binary search tree:
inserting all 26 single-letter words in sorted order (a→b→c→…→z) builds a fully degenerate
26-deep right chain off the root, verified directly (351 total comparisons — the
exact triangular-number cost of comparing every new letter against every previously-inserted one
in turn). delete is the same asymptotic cost as insert: one downward
walk, one upward pruning unwind. Space: exactly as many nodes as an equivalent
trie needs for the same word list (verified above — 12 nodes either way for this page's own demo
set), but each node here is a fixed char + isEnd + three pointers,
regardless of alphabet size, rather than a collection sized to the branching actually present —
predictable per-node cost instead of fewer nodes overall.
This site's guide, Choosing a Search Tree, places this entry alongside Trie and Radix Tree as answering the same different question the guide's seven comparison entries don't: storing strings and answering prefix queries by spending nodes on characters, not whole keys. It answers that question by turning each character's branch decision into a small binary search — one node holding one character and three pointers — instead of a trie's per-node array or map; the two structures need the identical node count for the same word list, so the real tradeoff is what each node costs to store, not how many exist.