Ternary Search Tree

One character per node and exactly three children. Lower and higher compare the same position; only the equal child advances — a BST and a trie meeting in the middle.

Search: O(log n + m)

3 pointers per node

Space: O(n)

Prefix-search capable

Words to insert

Then search for

Speed: 950ms

Step 1 of 0—

Tree — solid teal edges advance a character

Empty tree

equal (advances)lower / higherword ends here

Current Step

Click Play to begin

Complexity

Search:O(log n + m)

Insert:O(log n + m)

Space:O(n)

Pointers/node:3

m = key length, n = total characters stored

Key Concepts

Only equal advances the character position
3 pointers instead of a trie's 26 or 256
Insertion order matters — it shapes each position's BST
Keeps prefix search, unlike a hash table

Compare with the trie →

Knowledge Check

Question 1 of 3

What do the three children of a ternary search tree node mean?

Indexing

Hashing your keys…

DSAverse

Ternary Search Tree

Tree — solid teal edges advance a character

Current Step

Complexity

Key Concepts

Knowledge Check

Ternary Search Tree

Tree — solid teal edges advance a character

Current Step

Complexity

Key Concepts

Knowledge Check