Coding Interview PatternsImplement Trie (Prefix Tree)
MediumTrie

Implement Trie (Prefix Tree)

Explanation & Solution

Practice Problem

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:

  • Trie() — Initializes the trie object.
  • 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.
Input:operations = ["Trie","insert","search","search","startsWith","insert","search"], operands = [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
0
Trie
1
insert
2
search
3
search
4
startsWith
5
insert
6
search
Output:[null,null,true,false,true,null,true]
0
null
1
null
2
true
3
false
4
true
5
null
6
true

Explanation: The Trie is initialized, then "apple" is inserted. Searching for "apple" returns true, but "app" returns false since only "apple" was inserted. However, startsWith("app") returns true because "apple" starts with "app". After inserting "app", searching for "app" returns true.

Constraints

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

Approach

Trie pattern

1. Define the Trie Node Structure

  • Each Trie node has a children object (hash map) mapping characters to child nodes
  • Each node also has an isEnd boolean flag indicating whether it marks the end of a complete word

2. Insert a Word

  • Start at the root node
  • For each character in the word, check if a child node exists for that character
  • If not, create a new Trie node and add it as a child
  • Move to the child node and continue with the next character
  • After processing all characters, mark the last node's isEnd as true

3. Search for a Word

  • Use a helper _searchPrefix to traverse the trie character by character
  • If any character is missing from the children, return null
  • If the traversal completes, return the final node
  • For search, verify that the returned node is not null and isEnd is true

4. Check a Prefix with startsWith

  • Use the same _searchPrefix helper
  • For startsWith, we only need to verify the returned node is not null — we do not require isEnd to be true

Key Insight

  • A trie stores characters along edges, so common prefixes share the same path, making prefix queries extremely efficient
  • The isEnd flag distinguishes between a prefix that exists only as part of a longer word and a prefix that is itself a complete word
Time
O(m) per operation where m is the length of the word or prefix
Space
O(n * m) where n is the number of words and m is the average word length

Solution Code

Next
Design Add and Search Words Data Structure