Trie
vs
BST
Visualizer
CS455 — Algorithms & Structured Programming — SFBU
Insert
Search
Autocomplete
Insert
Quick load:
car, cat, card, care
App words
Mixed prefixes
Short words
Diverse first chars ⚡
Clear all
Trie
character-per-node · direct child map — work scales with word length
L
, not vocabulary size
words
0
nodes
1
chars stored
0
last op · node visits
—
Insert words to build the Trie
Trie is empty — insert or load a preset
Insert:
O(L)
— direct map lookup per character.
Binary Search Tree
word-per-node · ordered lexicographically (left < root < right) — work scales with vocabulary size
n
words
0
nodes
0
chars stored
0
last op · node visits
—
Insert words to build the BST
BST is empty — insert or load a preset
Insert:
O(L · h)
— string compare at each of h levels.
Why Trie wins for autocomplete
trie node (character)
bst node (whole word)
end of word (Trie)
3
frequency