How do you solve Implement Trie (Prefix Tree)?

Implement a TrieNode class with a dictionary mapping characters to child nodes and a boolean flag for end-of-word. The Trie class maintains a root node. Insert iterates through characters, creating nodes as needed. Search and startsWith traverse nodes according to input characters, returning true or false based on presence and end-of-word flags. This approach guarantees efficient prefix and exact word queries with O(m) time per operation.

What pattern does Implement Trie (Prefix Tree) use?

The Pattern: Trie (Prefix Tree) The Heuristic: Tries represent sets of strings as paths in a tree, enabling O(m) time prefix and exact match queries by sharing common prefixes and marking word boundaries explicitly.

Implement Trie (Prefix Tree) — Trie

Q: What is the time complexity of Implement Trie (Prefix Tree)?

O(m). Each operation (insert, search, startsWith) processes each character of the input string once, resulting in linear time proportional to the length of the word or prefix.

Problem

Implement a trie with insert, search, and startsWith methods to store and query strings efficiently.

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

Example

Input: insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")

Output: null, true, false, true, null, true

First, "apple" is inserted into the trie. Searching for "apple" returns true because it was inserted. Searching for "app" returns false because "app" was not inserted as a complete word. startsWith("app") returns true because "apple" starts with "app". Then "app" is inserted. Searching for "app" now returns true.

Approach

Straightforward Solution

A naive approach would store all words in a list and perform linear scans for search and prefix queries, resulting in O(n*m) time per query (n = number of words, m = length of word/prefix), which is inefficient for large datasets.

Core Observation

A trie is a tree-like data structure where each node represents a character and paths from the root to nodes represent prefixes of inserted words. This structure enables efficient prefix-based queries by sharing common prefixes among words.

Path to Optimal

Preview

The key recognition signals are 'insert', 'search', and 'startsWith' operations on strings, which indicate a Trie pattern…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement a TrieNode class with a dictionary mapping characters to child nodes and a boolean flag for end-of-word. The Trie class maintains a root node…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m)

Each operation (insert, search, startsWith) processes each character of the input string once, resulting in linear time proportional to the length of the word or prefix.

Space

O(n * m)

In the worst case, all inserted words are distinct with no shared prefixes, requiring storage proportional to the total number of characters across all words. Each node stores a dictionary of children, which can grow with the alphabet size and number of unique prefixes.

Solution

Python

1class TrieNode:
  def __init__(self):
      self.children = {}
      self.end_of_word = False
5
6class Trie:
  def __init__(self):
      self.root = TrieNode()
9
  def insert(self, word: str) -> None:
      curr = self.root
      for c in word:
          if c not in curr.children:
              curr.children[c] = TrieNode()
          curr = curr.children[c]
      curr.end_of_word = True
17
  def search(self, word: str) -> bool:
      curr = self.root
      for c in word:
          if c not in curr.children:
              return False
          curr = curr.children[c]
      return curr.end_of_word
25
  def startsWith(self, prefix: str) -> bool:
      curr = self.root
      for c in prefix:
          if c not in curr.children:
              return False
          curr = curr.children[c]
      return True

Step-by-Step Solution

1

Build TrieNode Structure to Represent Characters and Word Endings

2def __init__(self):
3    self.children = {}
4    self.end_of_word = False

Objective

To create a node structure that holds child nodes for each character and a flag indicating if the node marks the end of a word.

Key Insight

Each TrieNode acts as a branching point in the trie, with a dictionary mapping characters to child nodes enabling dynamic and sparse storage. The end_of_word flag is essential to differentiate between nodes that represent prefixes and those that represent complete words. This design supports efficient traversal and word boundary detection.

Interview Quick-Check

Core Logic

TrieNode stores children in a dictionary keyed by characters and a boolean flag to mark word completion.

Common Pitfalls & Bugs

Forgetting to initialize the children dictionary or the end_of_word flag leads to incorrect trie behavior.

2

Initialize Trie with a Root Node

To set up the Trie data structure with a root node that serves as the starting point for all operations.

3

Insert Words by Creating or Traversing Child Nodes

To add words to the trie by iterating through each character and creating nodes as needed.

4

Search for Exact Words by Traversing Nodes and Checking End Flags

To determine if a word exists in the trie by following nodes for each character and verifying the end_of_word flag.

5

Check Prefix Existence by Traversing Nodes Without End Flag Requirement

To verify if any word in the trie starts with a given prefix by traversing nodes for each prefix character.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 3 Critical

self.children = {}

Create an empty dictionary to hold child nodes keyed by characters.

Using a dictionary allows efficient O(1) average lookup and insertion of child nodes for each character, supporting sparse and dynamic branching.

Full line-by-line criticality + rationale for all 27 lines available on Pro.

Test Your Understanding

Why does the Trie use a boolean flag at nodes instead of just relying on the presence of children to determine if a word exists?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Implement Trie (Prefix Tree) from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Implement Trie (Prefix Tree) drill

or drill a free problem

1	`class TrieNode:`
2	`def __init__(self):`
3	`self.children = {}`
4	`self.end_of_word = False`
5
6	`class Trie:`
7	`def __init__(self):`
8	`self.root = TrieNode()`
9
10	`def insert(self, word: str) -> None:`
11	`curr = self.root`
12	`for c in word:`
13	`if c not in curr.children:`
14	`curr.children[c] = TrieNode()`
15	`curr = curr.children[c]`
16	`curr.end_of_word = True`
17
18	`def search(self, word: str) -> bool:`
19	`curr = self.root`
20	`for c in word:`
21	`if c not in curr.children:`
22	`return False`
23	`curr = curr.children[c]`
24	`return curr.end_of_word`
25
26	`def startsWith(self, prefix: str) -> bool:`
27	`curr = self.root`
28	`for c in prefix:`
29	`if c not in curr.children:`
30	`return False`
31	`curr = curr.children[c]`
32	`return True`