Skip to main content
Talentd

Implement Trie (Prefix Tree) - Solution & Explanation

MediumHash TableStringDesignTrie34 min readAsked at: Amazon, Microsoft, Apple +18
Practice this problem

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:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

 

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.

Approach Overview

Problem Overview: Design a Trie (Prefix Tree) that supports three operations: insert(word), search(word), and startsWith(prefix). Each operation must efficiently process strings by sharing common prefixes across stored words.

Approach 1: Native Trie with Fixed Children Array (O(L) time per operation)

This approach builds a classic Trie where each node stores an array of size 26 for lowercase English letters. During insert, iterate through the characters of the word and create nodes if they don't exist. For search and startsWith, traverse the tree following character indexes. The key insight is prefix sharing: multiple words reuse the same nodes until their paths diverge. Each operation runs in O(L) time where L is the word length, because you process one character at a time. Space complexity is O(N * L) in the worst case for storing all characters across inserted words. This implementation is extremely fast due to constant-time array access.

Approach 2: Trie Using Hash Maps (O(L) time per operation)

Instead of allocating a fixed array of 26 children, each node stores a dynamic map (hash table) from character to child node. While inserting a word, check the map for the next character and create a node only when necessary. search and startsWith follow the same traversal logic but rely on hash lookups. The time complexity remains O(L) per operation, but space becomes more efficient for sparse datasets because nodes only store existing edges. The tradeoff is slightly slower lookups due to hashing compared to array indexing. This approach combines concepts from hash tables and tries and is easier to generalize when the character set is large.

Both approaches exploit prefix compression: shared prefixes reduce redundant storage and allow quick prefix checks. This makes Tries particularly effective for autocomplete systems, dictionary lookups, and prefix-based search features.

Recommended for interviews: The fixed-array Trie is the implementation most interviewers expect. It demonstrates clear understanding of data structure design and delivers predictable O(L) operations with minimal overhead. The hash-map variant is useful when the character set is large or memory usage matters. Showing both approaches signals strong understanding of tradeoffs.

Approach 1: Native Trie Implementation

This approach involves creating a basic Trie data structure using a tree of nodes. Each node represents a character in a word. Starting from a root node, each character of the word is inserted sequentially, with branches representing the progression to subsequent characters. This forms a chain of nodes (linked in a tree-like manner) from the root to the nodes representing complete words. For searching, we traverse these nodes based on the characters of the input word or prefix to check for existence.

We first define a TrieNode structure with a children array to hold 26 letters and a boolean isEndOfWord to check if a node marks the end of a word. The createNode function initializes each node. TrieCreate initializes the trie by setting the root node.

The methods work by converting each character of the word or prefix into an index (0-25 for 'a'-'z'), navigating the children array of nodes for insertion or search operations. The insert function loops through each character, generating nodes along the path if needed, setting the isEndOfWord flag at the end. The search verifies both existence and termination of the string in the Trie, while startsWith logic only requires the prefix traversal.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: Insert, search, and startsWith operations are O(m), where m is the length of the word/prefix.
Space Complexity: O(26 * n * m) in the worst case, where n is the number of inserted words and m is the average length of the words. Each insertion can potentially add m nodes with 26 possible children each.

Try this approach in the editor →

Approach 2: Comprehensive Trie using Maps

This approach relies on maps (or hashmaps) for storing children nodes dynamically. The advantage of using maps over arrays in this context arises from reduced space consumption when handling sparse trees since only existing characters are stored. Nodes manage their children using hash references, leading to more flexible branching.

This C++ implementation employs unordered_map in place of fixed-arrays to maintain child nodes in a Trie. Each TrieNode can dynamically allocate space only for characters that appear, leading to memory efficiency especially when nodes have very few immediate child nodes compared to the alphabet size. Insert, search, and startsWith operate similarly as before, now using map functionalities (find) to identify existing children and allocate if necessary.

Code

C++PythonJavaScript

C++

Python

JavaScript

Complexity

Time Complexity: O(m) per operation where m is the word/prefix length.
Space Complexity: O(n * m), where n estimates the word count and m accounts for varying lengths since nodes only maintain necessary mappings.

Try this approach in the editor →

Approach 3: Default Approach

We start from the root of the trie and insert the string. For the child node corresponding to the current character, there are two cases:

  • The child node exists. Move along the pointer to the child node and continue processing the next character.
  • The child node does not exist. Create a new child node, record it in the corresponding position of the children array, then move along the pointer to the child node and continue searching for the next character.

Repeat the above steps until the last character of the string is processed, then mark the current node as the end of the string.

2. Search for a Prefix

We start from the root of the trie and search for the prefix. For the child node corresponding to the current character, there are two cases:

  • The child node exists. Move along the pointer to the child node and continue searching for the next character.
  • The child node does not exist. This means the trie does not contain the prefix, so return a null pointer.

Repeat the above steps until a null pointer is returned or the last character of the prefix is searched.

If we search to the end of the prefix, it means the trie contains the prefix. Additionally, if the isEnd of the node corresponding to the end of the prefix is true, it means the trie contains the string.

The time complexity for inserting a string is O(m times |\Sigma|), and the time complexity for searching a prefix is O(m), where m is the length of the string and |\Sigma| is the size of the character set (26 in this problem). The space complexity is O(q times m times |\Sigma|), where q is the number of inserted strings.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Native Trie Implementation

Time Complexity: Insert, search, and startsWith operations are O(m), where m is the length of the word/prefix.
Space Complexity: O(26 * n * m) in the worst case, where n is the number of inserted words and m is the average length of the words. Each insertion can potentially add m nodes with 26 possible children each.

Comprehensive Trie using Maps

Time Complexity: O(m) per operation where m is the word/prefix length.
Space Complexity: O(n * m), where n estimates the word count and m accounts for varying lengths since nodes only maintain necessary mappings.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Native Trie with Fixed ArrayO(L) per operationO(N * L)Standard interview solution when alphabet size is fixed (e.g., lowercase letters)
Trie Using Hash MapsO(L) averageO(N * L)Better when character set is large or the trie is sparse

Video Solution

Implement Trie (Prefix Tree) - Leetcode 208 • NeetCode • 310,413 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Implement Trie (Prefix Tree) easy or hard?
Implement Trie (Prefix Tree) is rated Medium because the idea is simple but requires careful data structure design. Candidates must correctly manage node creation, prefix traversal, and word termination flags while keeping operations efficient.
Implement Trie (Prefix Tree) Python/Java solution
In Python or Java, implement a TrieNode class containing children references and a boolean end-of-word flag. The Trie class manages insert, search, and startsWith by traversing nodes character by character. Each method processes the string sequentially, giving O(L) time complexity.
How to solve Implement Trie (Prefix Tree) in O(n)?
The problem is solved using a Trie where operations depend only on the length of the word being processed. By traversing characters sequentially and storing children pointers for each character, insert, search, and prefix checks all run in O(L) time. This avoids scanning all stored words, which would be much slower.
What is the best approach for Implement Trie (Prefix Tree)?
The standard solution uses a Trie with a fixed array of 26 children per node for lowercase English letters. Each operation (insert, search, startsWith) traverses characters one by one, giving O(L) time where L is the word length. Array indexing makes it faster than map-based implementations in most interview scenarios.
Is Implement Trie (Prefix Tree) asked at Google/Amazon/Meta?
Trie design questions frequently appear in interviews at companies like Google, Amazon, Meta, and Microsoft. Variations include autocomplete systems, word dictionaries with wildcards, and prefix-based search structures. Understanding Trie traversal and node design is commonly tested.
What data structure is used in Implement Trie (Prefix Tree)?
The core data structure is a Trie (prefix tree). Each node represents a character and stores references to child nodes plus a flag marking the end of a word. Implementations typically use either a fixed array of children or a hash map for dynamic branching.
What is the time complexity of Implement Trie (Prefix Tree)?
Each operation runs in O(L) time where L is the length of the input string. Insert creates nodes while traversing characters, search verifies a full path, and startsWith checks whether a prefix path exists. Space complexity is O(N * L) in the worst case for storing all inserted words.

Ready to solve this problem?

Practice Implement Trie (Prefix Tree) with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Prefix and Suffix Pairs I

Next

Count Prefix and Suffix Pairs II