Implement Trie (Prefix Tree) solution and explanation
Google
9 more videos on this problem
Implement Trie (Prefix Tree) - Leetcode 208NeetCode · 18:56 · 310K views
Implement Trie (Prefix Tree) | Microsoft | Leetcode - 208codestorywithMIK · 31:00 · 27K views
Implement Trie (Prefix Tree) - Leetcode 208 - Trees (Python)Greg Hogg · 9:30 · 15K views
Trie Data Structure | LeetCode 208. Implement Trie (Prefix Tree) - Interview Prep Ep 83Fisher Coder · 17:20 · 2K views
Implement Trie (Prefix Tree) - LeetCode 202 - PythonDeepti Talesra · 20:17 · 2K views
Implement Trie (Prefix Tree) - 208. LeetCode - JavaTeddy Smith · 12:33 · 1K views
Implement Trie (Prefix Tree) | Day 14 | [May LeetCoding Challenge] [Leetcode 208] [2020]Algorithms Made Easy · 4:23 · 1K views
Implement Trie Prefix Tree | LeetCode 208 (Medium)Destination FAANG · 25:19 · 938 views
208. Implement Trie (Prefix Tree) | LeetCode Daily Challenge | LeetCode POTDDeep Tech · 17:53 · 749 views
208. Implement Trie (Prefix Tree) | JavaScript | Detailed Explanation | LeetCode Daily ChallengeLeetCodeWithMonu · 15:34 · 534 views
The problem
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 stringwordinto the trie.boolean search(String word)Returnstrueif the stringwordis in the trie (i.e., was inserted before), andfalseotherwise.boolean startsWith(String prefix)Returnstrueif there is a previously inserted stringwordthat has the prefixprefix, andfalseotherwise.
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 <= 2000wordandprefixconsist only of lowercase English letters.- At most
3 * 104calls in total will be made toinsert,search, andstartsWith.
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.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return Trueclass TrieNode {
public TrieNode[] children;
public boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26];
isEndOfWord = false;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
int index = ch - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return node.isEndOfWord;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char ch : prefix.toCharArray()) {
int index = ch - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return true;
}
}class TrieNode {
public:
TrieNode* children[26];
bool isEndOfWord;
TrieNode() {
isEndOfWord = false;
for (int i = 0; i < 26; ++i) {
children[i] = nullptr;
}
}
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEndOfWord = true;
}
bool search(string word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
return false;
}
node = node->children[index];
}
return node->isEndOfWord;
}
bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
int index = c - 'a';
if (!node->children[index]) {
return false;
}
node = node->children[index];
}
return true;
}
};class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
}
search(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return node.isEndOfWord;
}
startsWith(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return true;
}
}typedef struct TrieNode {
struct TrieNode *children[26];
bool isEndOfWord;
} TrieNode;
TrieNode* createNode() {
TrieNode *node = (TrieNode *)malloc(sizeof(TrieNode));
node->isEndOfWord = false;
for(int i = 0; i < 26; i++)
node->children[i] = NULL;
return node;
}
typedef struct {
TrieNode *root;
} Trie;
Trie* trieCreate() {
Trie *trie = (Trie *)malloc(sizeof(Trie));
trie->root = createNode();
return trie;
}
void trieInsert(Trie* obj, char * word) {
TrieNode *node = obj->root;
while (*word) {
int index = *word - 'a';
if (!node->children[index])
node->children[index] = createNode();
node = node->children[index];
word++;
}
node->isEndOfWord = true;
}
bool trieSearch(Trie* obj, char * word) {
TrieNode *node = obj->root;
while (*word) {
int index = *word - 'a';
if (!node->children[index])
return false;
node = node->children[index];
word++;
}
return node->isEndOfWord;
}
bool trieStartsWith(Trie* obj, char * prefix) {
TrieNode *node = obj->root;
while (*prefix) {
int index = *prefix - 'a';
if (!node->children[index])
return false;
node = node->children[index];
prefix++;
}
return true;
}
void trieFree(Trie* obj) {
// A function to recursively free nodes would be here if needed.
free(obj);
}public class TrieNode {
public TrieNode[] children = new TrieNode[26];
public bool isEndOfWord;
public TrieNode() {
isEndOfWord = false;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void Insert(string word) {
TrieNode node = root;
foreach (char c in word) {
int index = c - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEndOfWord = true;
}
public bool Search(string word) {
TrieNode node = root;
foreach (char c in word) {
int index = c - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return node.isEndOfWord;
}
public bool StartsWith(string prefix) {
TrieNode node = root;
foreach (char c in prefix) {
int index = c - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return true;
}
}In the Python implementation, we make use of a TrieNode class with a dictionary to store pointers to child nodes and a boolean attribute to denote if the node is the end of a word. The Trie class creates the root node as part of the constructor. The insert method processes the word character by character, adding nodes for characters that are missing in the current sequence. The search and startsWith methods traverse down the trie nodes based on the characters of word or prefix, verifying each node's presence accordingly and checking the is_end_of_word flag when necessary for search.
Time Complexity: O(m) for insert, search, and startsWith operations, where m denotes the length of the word or prefix.
Space Complexity: Depends on actual word storage, but typically O(k * n), where k is the length of the longest word and n is the number of nodes. The Trie can branch widely at each node due to dynamic hashmap allocations.
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.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
node = node.children.setdefault(char, TrieNode())
node.is_end_of_word = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True#include <unordered_map>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool isEndOfWord;
TrieNode() : isEndOfWord(false) {}
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->isEndOfWord = true;
}
bool search(string word) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
return false;
}
node = node->children[c];
}
return node->isEndOfWord;
}
bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
if (node->children.find(c) == node->children.end()) {
return false;
}
node = node->children[c];
}
return true;
}
};class TrieNode {
constructor() {
this.children = new Map();
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (let char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
node.isEndOfWord = true;
}
search(word) {
let node = this.root;
for (let char of word) {
if (!node.children.has(char)) {
return false;
}
node = node.children.get(char);
}
return node.isEndOfWord;
}
startsWith(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children.has(char)) {
return false;
}
node = node.children.get(char);
}
return true;
}
}In this Python solution, each TrieNode contains a dictionary (children) providing direct access to only required child characters. This approach optimizes storage, especially reducing overhead when branching is sparse. The root provides the base node in the Trie. The insert method applies setdefault for dictionary operation - simplifying conditional insertion logic. Both search and startsWith check the presence of each character in sequence traversing the root to target node, utilizing dictionary fast access and probing methods.
Time Complexity: Each of insert, search, startsWith are O(m), m being the length of inserted/searched/checked strings.
Space Complexity: With dictionary, space becomes O(n) typical due to flexibility in required children across n words.
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
childrenarray, 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.
class TrieNode {
children;
isEnd;
constructor() {
this.children = new Array(26);
this.isEnd = false;
}
}
class Trie {
root;
constructor() {
this.root = new TrieNode();
}
insert(word: string): void {
let head = this.root;
for (let char of word) {
let index = char.charCodeAt(0) - 97;
if (!head.children[index]) {
head.children[index] = new TrieNode();
}
head = head.children[index];
}
head.isEnd = true;
}
search(word: string): boolean {
let head = this.searchPrefix(word);
return head != null && head.isEnd;
}
startsWith(prefix: string): boolean {
return this.searchPrefix(prefix) != null;
}
private searchPrefix(prefix: string) {
let head = this.root;
for (let char of prefix) {
let index = char.charCodeAt(0) - 97;
if (!head.children[index]) return null;
head = head.children[index];
}
return head;
}
}type Trie struct {
children [26]*Trie
isEnd bool
}
func Constructor() Trie {
return Trie{}
}
func (this *Trie) Insert(word string) {
node := this
for _, c := range word {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = &Trie{}
}
node = node.children[idx]
}
node.isEnd = true
}
func (this *Trie) Search(word string) bool {
node := this.SearchPrefix(word)
return node != nil && node.isEnd
}
func (this *Trie) StartsWith(prefix string) bool {
node := this.SearchPrefix(prefix)
return node != nil
}
func (this *Trie) SearchPrefix(s string) *Trie {
node := this
for _, c := range s {
idx := c - 'a'
if node.children[idx] == nil {
return nil
}
node = node.children[idx]
}
return node
}
/**
* Your Trie object will be instantiated and called as such:
* obj := Constructor();
* obj.Insert(word);
* param_2 := obj.Search(word);
* param_3 := obj.StartsWith(prefix);
*/use std::{cell::RefCell, collections::HashMap, rc::Rc};
struct TrieNode {
pub val: Option<char>,
pub flag: bool,
pub child: HashMap<char, Rc<RefCell<TrieNode>>>,
}
impl TrieNode {
fn new() -> Self {
Self {
val: None,
flag: false,
child: HashMap::new(),
}
}
fn new_with_val(val: char) -> Self {
Self {
val: Some(val),
flag: false,
child: HashMap::new(),
}
}
}
struct Trie {
root: Rc<RefCell<TrieNode>>,
}
/// Your Trie object will be instantiated and called as such:
/// let obj = Trie::new();
/// obj.insert(word);
/// let ret_2: bool = obj.search(word);
/// let ret_3: bool = obj.starts_with(prefix);
impl Trie {
fn new() -> Self {
Self {
root: Rc::new(RefCell::new(TrieNode::new())),
}
}
fn insert(&self, word: String) {
let char_vec: Vec<char> = word.chars().collect();
// Get the clone of current root node
let mut root = Rc::clone(&self.root);
for c in &char_vec {
if !root.borrow().child.contains_key(c) {
// We need to manually create the entry
root.borrow_mut()
.child
.insert(*c, Rc::new(RefCell::new(TrieNode::new())));
}
// Get the child node
let root_clone = Rc::clone(root.borrow().child.get(c).unwrap());
root = root_clone;
}
{
root.borrow_mut().flag = true;
}
}
fn search(&self, word: String) -> bool {
let char_vec: Vec<char> = word.chars().collect();
// Get the clone of current root node
let mut root = Rc::clone(&self.root);
for c in &char_vec {
if !root.borrow().child.contains_key(c) {
return false;
}
// Get the child node
let root_clone = Rc::clone(root.borrow().child.get(c).unwrap());
root = root_clone;
}
let flag = root.borrow().flag;
flag
}
fn starts_with(&self, prefix: String) -> bool {
let char_vec: Vec<char> = prefix.chars().collect();
// Get the clone of current root node
let mut root = Rc::clone(&self.root);
for c in &char_vec {
if !root.borrow().child.contains_key(c) {
return false;
}
// Get the child node
let root_clone = Rc::clone(root.borrow().child.get(c).unwrap());
root = root_clone;
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Native Trie Implementation | Time Complexity: O(m) for insert, search, and startsWith operations, where m denotes the length of the word or prefix. |
| Comprehensive Trie using Maps | Time Complexity: Each of insert, search, startsWith are O(m), m being the length of inserted/searched/checked strings. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Native Trie with Fixed Array | O(L) per operation | O(N * L) | Standard interview solution when alphabet size is fixed (e.g., lowercase letters) |
| Trie Using Hash Maps | O(L) average | O(N * L) | Better when character set is large or the trie is sparse |
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.