How do you approach Implement Trie?

Use a tree structure where each node has children for each letter.

What is the time complexity of Implement Trie?

Time complexity: O(m) per operation where m is the word/prefix length. Space complexity: O(total characters inserted).

What are common mistakes on Implement Trie?

Leaving out the end-of-word flag, so a lookup reports words that were never inserted. Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest. Not handling the empty string, which is a valid prefix of everything.

gitGood.dev

← Back to problems

Implement Trie

MediumData Structures

Description

A **trie** (pronounced as "try") or **prefix tree** is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: - `insert(word)` inserts the string `word` into the trie. - `search(word)` returns `true` if the string `word` is in the trie (i.e., was inserted before), and `false` otherwise. - `startsWith(prefix)` returns `true` if there is a previously inserted string `word` that has the prefix `prefix`, and `false` otherwise. **Note:** For this problem, implement operations as a function that takes a list of commands and returns the results. Return `null` for void operations (insert).

Example 1

Input: operations = [["insert","apple"],["search","apple"],["search","app"],["startsWith","app"],["insert","app"],["search","app"]]

Output: [null,true,false,true,null,true]

Constraints

- 1 <= word.length, prefix.length <= 2000 - word and prefix consist only of lowercase English letters. - At most 3 * 10^4 total calls will be made to insert, search, and startsWith.

Implement Trie: approach, complexity and pitfalls

A medium trie problem, graded against 6 test cases (3 of them hidden).

The pattern: Trie

A prefix tree for fast string lookup by shared prefix.

Reach for it when you see: Many words, repeated prefix queries, autocomplete, or word-search over a grid.

More Trieproblems →

If you are stuck

Show the 3-step hint ladder

Use a tree structure where each node has children for each letter.
Each node needs a flag to indicate if it marks the end of a word.
For startsWith, you only need to verify the path exists - no need to check the end flag.

The optimal approach

Show the approach: Trie with Hash Map Children

Each node stores a map of children (letter -> node) and an end-of-word flag. Insert creates nodes as needed. Search follows the path and checks the end flag. StartsWith follows the path without checking the end flag.

Time: O(m) per operation where m is the word/prefix length
Space: O(total characters inserted)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Trie mistakes

These apply to the pattern as a whole, not just this problem.

Leaving out the end-of-word flag, so a lookup reports words that were never inserted.
Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest.
Not handling the empty string, which is a valid prefix of everything.