Implement Trie (Prefix Tree)

Implement a trie with insert(word), search(word) and startsWith(prefix). (In the playground, each line is one operation.)

A way to picture it

Think of a phone's autocomplete as a tree of letters. Typing “c-a” walks two steps down from the root, and every word below that spot starts with “ca”. A ★ on a node means a whole word ends right there.

How to approach it

Each node maps a letter to a child and has an end-of-word flag. Words sharing a prefix share the path. search needs the flag; startsWith doesn't.

Example

Input: {"ops":["insert apple","search apple","search app","startsWith app","insert app","search app"]}. Output: [null,true,false,true,null,true].

Complexity: O(L) per operation time and O(total letters) space. L is the word length; each letter is one step.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.