Trie Delete
Unmark the terminal. Prune nodes upward while they have no children and are not terminal.
Trie: Delete a word and prune its tail
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.
Cost
- Best
- O(L)
- Average
- O(L)
- Worst
- O(L)
- Space
- O(L)
Before this
Taught by the same lesson
Trie covers these too, in the same run.