AlgoScope

Trie

A tree with one node per character, so every path from the root spells a prefix and words share their common prefixes.

Data structures, data structure, intermediateAlso called prefix tree
Follow existing child c.•carnode
Follow existing child c.•carnode

Trie: Insert words sharing prefixes

Decision, step 6 of 19

"cart", letter 'c'. The current node already has a child 'c', shared with an earlier word, so follow it.

Cost

Insert
O(L)
Search
O(L)
Prefix query
O(L + results)
Space
O(total characters * alphabet)

L is the word length.

Leads to

Topics that need this one first.

Taught by the same lesson

Trie covers these too, in the same run.