AlgoScope

Prefix Search and Autocomplete

Walk the prefix, then enumerate every terminal below it with a DFS.

String algorithms, algorithm, intermediate
Follow a.•carttdog
Follow a.•carttdog

Trie: Autocomplete: everything under ca

Step, step 3 of 7

Letter 'a': follow it.

How trie works

Cost

Best
O(L)
Average
O(L + results)
Worst
O(L + subtree)
Space
O(depth)

Taught by the same lesson

Trie covers these too, in the same run.