AlgoScope

Trie Delete

Unmark the terminal. Prune nodes upward while they have no children and are not terminal.

String algorithms, algorithm, intermediate
Found cart, unmarking it.•carttdognode
Found cart, unmarking it.•carttdognode

Trie: Delete a word and prune its tail

Decision, step 2 of 5

Walking "cart" reaches its last node, which is terminal. Drop that mark: the word is gone, though its letters may still be needed by other words.

How trie works

Cost

Best
O(L)
Average
O(L)
Worst
O(L)
Space
O(L)

Taught by the same lesson

Trie covers these too, in the same run.