Log inSign up
mediumLeetCodeNot Started

Implement Trie (Prefix Tree)

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on LeetCode
Lesson

Problem Statement

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. - void insert(String word) Inserts the string word into the trie. - boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. - boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1 · Example 1: Standard Trie operations:

Input: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output: [null, null, true, false, true, null, true]
Explanation: 1. insert("apple") 2. search("apple") -> true 3. search("app") -> false (node exists, but isEnd is false) 4. startsWith("app") -> true (path exists) 5. insert("app") 6. search("app") -> true (now isEnd is true) Trie Tree: (root) | a | p | p* (isEnd after insert("app")) | l | e* (isEnd)

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Construct a fundamental Trie node with pointer array and termination flag.
  • Differentiate between search (requires isEnd) and startsWith (requires only path validity).
  • Analyze the asymptotic trade-offs between Hash Tables and Tries.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • String dataset requires prefix searching (autocomplete / dictionary matching).
  • Operations must be faster than hash tables for prefix matching.
  • Deterministic O(L) query time independent of dataset size N.

Algorithmic Decision Tree:

  • Use a Trie when prefix matching is needed; hash tables cannot do prefix matching without full scans.
  • Store children[26] directly for lowercase alphabets to achieve O(1) character lookup.
  • Mark isEnd = true at the terminating character node of inserted words.

Connected Patterns:

Design Add and Search Words Data StructureWord Search IIReplace Words

1. Dynamic Array Storage with Full Scan

Intuition

Append words into vector<string>. For search(word), check if w == word. For startsWith(prefix), check if w.find(prefix) == 0. Scans up to N words each time.

When to apply: Toy implementation for small test cases.

Algorithm

  1. Step 1: Maintain list of words.
  2. Step 2: insert: add to list.
  3. Step 3: search: linear scan for exact match.
  4. Step 4: startsWith: linear scan for prefix match.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6class Trie {
7 vector<string> dict;
8public:
9 Trie() {}
10
11 void insert(string word) {
12 dict.push_back(word);
13 }
14
15 bool search(string word) {
16 for (const string& w : dict) {
17 if (w == word) return true;
18 }
19 return false;
20 }
21
22 bool startsWith(string prefix) {
23 for (const string& w : dict) {
24 if (w.rfind(prefix, 0) == 0) return true;
25 }
26 return false;
27 }
28};
29
30int main() {
31 Trie trie;
32 trie.insert("apple");
33 cout << "search('apple'): " << (trie.search("apple") ? "true" : "false") << endl;
34 cout << "search('app'): " << (trie.search("app") ? "true" : "false") << endl;
35 cout << "startsWith('app'): " << (trie.startsWith("app") ? "true" : "false") << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: insert: O(1), search: O(N * L), startsWith: O(N * L) — Must inspect every word in the list for search and prefix queries.
  • Space complexity: O(N * L) — Stores all N words in memory.

Why Brute Force Doesn't Scale:

With 30,000 words and 30,000 queries, brute force executes 9 * 108 string operations.

A 26-ary Trie answers each query in exactly L pointer dereferences (e.g., <= 10 steps), running in sub-milliseconds.

2. Hash Set Exact Match with Hash Set of Prefixes

Intuition

Two hash sets: exactSet and prefixSet. Inserting word inserts word into exactSet and all L prefixes into prefixSet. Both queries run in O(L) time.

When to apply: Fast lookups when word lengths are small.

Algorithm

  1. Step 1: Set 1 stores full words.
  2. Step 2: Set 2 stores all prefix substrings.
  3. Step 3: insert: add word to Set 1 and all prefixes to Set 2.
  4. Step 4: search: lookup in Set 1.
  5. Step 5: startsWith: lookup in Set 2.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_set>
4using namespace std;
5
6class Trie {
7 unordered_set<string> exactWords;
8 unordered_set<string> prefixes;
9public:
10 Trie() {}
11
12 void insert(string word) {
13 exactWords.insert(word);
14 string pref = "";
15 for (char c : word) {
16 pref += c;
17 prefixes.insert(pref);
18 }
19 }
20
21 bool search(string word) {
22 return exactWords.count(word) > 0;
23 }
24
25 bool startsWith(string prefix) {
26 return prefixes.count(prefix) > 0;
27 }
28};
29
30int main() {
31 Trie trie;
32 trie.insert("apple");
33 cout << "search('apple'): " << (trie.search("apple") ? "true" : "false") << endl;
34 cout << "startsWith('app'): " << (trie.startsWith("app") ? "true" : "false") << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: insert: O(L^2), search: O(L), startsWith: O(L) — Slicing and inserting all L prefixes takes O(L2) time.
  • Space complexity: O(N * L^2) — Stores all prefix substrings in hash set.

3. Standard 26-ary Trie (Prefix Tree)

Intuition

Each node holds children[26] and isEnd. insert walks character by character, allocating new nodes when child pointers are null, and sets isEnd = true at the final node. search returns curr != null && curr.isEnd. startsWith returns curr != null.

When to apply: Standard interview and industry solution for LeetCode 208.

Algorithm

  1. Step 1: Define TrieNode with array children[26] (initialized to null) and boolean isEnd = false.
  2. Step 2: insert(word): walk from root. If children[char - 'a'] is null, allocate new node. Move curr. At word end, set curr.isEnd = true.
  3. Step 3: search(word): walk characters. If child is null, return false. At end, return curr.isEnd.
  4. Step 4: startsWith(prefix): walk characters. If child is null, return false. If loop finishes, return true.

Interactive Trace for LeetCode 208 Trie Operations

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: insert('apple')
Visual state
Values and pointers at this exact step
tree
Root
(root)
char 'a'
'a'
char 'p'
'p'
char 'p'
'p' (isEnd: false)
char 'e'*
'e'* (isEnd: true)

Node order shown; add connections to display explicit tree edges.

path: p2
Check / comparison
Node 'e' marked with isEnd = true
Decision / next transition
Word 'apple' inserted.
Why this step matters

Step 1: insert(apple). Create path root -> a -> p -> p -> l -> e. Set isEnd = true on node e.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3using namespace std;
4
5struct TrieNode {
6 TrieNode* children[26];
7 bool isEnd;
8 TrieNode() : isEnd(false) {
9 for (int i = 0; i < 26; i++) children[i] = nullptr;
10 }
11};
12
13class Trie {
14 TrieNode* root;
15public:
16 Trie() {
17 root = new TrieNode();
18 }
19
20 void insert(string word) {
21 TrieNode* curr = root;
22 for (char c : word) {
23 int idx = c - 'a';
24 if (!curr->children[idx]) {
25 curr->children[idx] = new TrieNode();
26 }
27 curr = curr->children[idx];
28 }
29 curr->isEnd = true;
30 }
31
32 bool search(string word) {
33 TrieNode* curr = root;
34 for (char c : word) {
35 int idx = c - 'a';
36 if (!curr->children[idx]) return false;
37 curr = curr->children[idx];
38 }
39 return curr->isEnd;
40 }
41
42 bool startsWith(string prefix) {
43 TrieNode* curr = root;
44 for (char c : prefix) {
45 int idx = c - 'a';
46 if (!curr->children[idx]) return false;
47 curr = curr->children[idx];
48 }
49 return true;
50 }
51};
52
53int main() {
54 Trie trie;
55 trie.insert("apple");
56 cout << "Optimal search('apple'): " << (trie.search("apple") ? "true" : "false") << endl;
57 cout << "Optimal search('app'): " << (trie.search("app") ? "true" : "false") << endl;
58 cout << "Optimal startsWith('app'): " << (trie.startsWith("app") ? "true" : "false") << endl;
59 trie.insert("app");
60 cout << "Optimal search('app') after insert: " << (trie.search("app") ? "true" : "false") << endl;
61 return 0;
62}

Time & Space Complexity

  • Time complexity: All operations: O(L) — All operations touch exactly L characters, doing O(1) array lookups per step.
  • Space complexity: O(Total inserted characters * 26) — Worst case allocates up to L nodes per inserted word with 26 pointers each.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Dynamic Array of Stringsinsert: O(1), search: O(N * L), startsWith: O(N * L)O(N * L)Store words in vector<string>. On search or startsWith, scan all N words in the array.Linear scan across all stored words.
2.Better — Hash Set for Exact Match + Array Scan for Prefixinsert: O(L), search: O(L), startsWith: O(N * L)O(N * L)Use unordered_set<string> for O(L) exact search, but startsWith still requires scanning keys.Inability of hash sets to query prefixes without full traversal.
3.Optimal — 26-ary Trie (Prefix Tree)OptimalAll operations strictly O(L)O(Sum of word lengths * 26)Characters branch via 26-element pointer arrays. Traversal is O(1) per character for all operations.None. Canonical data structure for prefix retrieval.

Common Pitfalls & Crucial Edge Cases

Confusing `search` and `startsWith`

search requires curr.isEnd == true, whereas startsWith only requires reaching the end of the prefix without null pointers.

Index calculation error

Forgetting - 'a' or - 97 when indexing into children array.

Allocating new nodes during search

Accidental mutation of Trie structure during read-only queries.

Crucial Edge Cases to Validate:

  • Single letter word ('a') — Successfully inserts into root's children and sets isEnd = true.
  • Searching a prefix that is not a word — search returns false while startsWith returns true.
  • Long string (length 2000) — Clean linear loop without deep recursion or stack overflow.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly differentiate search from startsWith upfront in your explanation.
  2. Explain the trade-off: a Hash Table is O(1) average time but cannot perform prefix matching without checking all keys, whereas a Trie is deterministic O(L) for both exact and prefix searches.
  3. Mention that fixed 26-ary arrays provide maximum speed due to cache locality, while hash maps in Python/JS offer space efficiency for large alphabets (e.g., Unicode).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the key difference in implementation between search and startsWith in a Trie?

2.Why is Trie preferred over a Hash Table for autocomplete systems?

Back to DSA Sheet