Implement Trie (Prefix Tree)

🧩 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 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

🔍 Approaches

1. N-ary Tree with Array/Map ($O(L)$)

• Concept: Each node represents a character. It has:
• children: A collection (Array of size 26 or Hash Map) mapping next character to next Node.
• isEnd: A boolean flag indicating if a word ends at this node.
• Operations:
• Insert: Traverse down the tree, creating nodes if they don't exist. Mark last node isEnd = true.
• Search: Traverse down. If we get stuck (child null), return false. Return isEnd at the final node.
• StartsWith: Traverse down. If we get stuck, return false. If we finish the prefix, return true.

⏳ Time & Space Complexity

• Time Complexity: $O(L)$ for all operations, where $L$ is valid length of the string.
• Space Complexity: $O(N \cdot L)$, where $N$ is number of words and $L$ is average length.

🚀 Code Implementations

C++

#include <iostream>
#include <vector>
using namespace std;
class TrieNode {
public:
TrieNode* children[26];
bool isEnd;
TrieNode() {
isEnd = false;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
class Trie {
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* curr = root;
for (char c : word) {
int idx = c - 'a';
if (!curr->children[idx]) {
curr->children[idx] = new TrieNode();
}
curr = curr->children[idx];
}
curr->isEnd = true;
}
bool search(string word) {
TrieNode* curr = root;
for (char c : word) {
int idx = c - 'a';
if (!curr->children[idx]) return false;
curr = curr->children[idx];
}
return curr->isEnd;
}
bool startsWith(string prefix) {
TrieNode* curr = root;
for (char c : prefix) {
int idx = c - 'a';
if (!curr->children[idx]) return false;
curr = curr->children[idx];
}
return true;
}
};

Python

class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
curr = self.root
for char in word:
if char not in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.is_end = True
def search(self, word: str) -> bool:
curr = self.root
for char in word:
if char not in curr.children:
return False
curr = curr.children[char]
return curr.is_end
def startsWith(self, prefix: str) -> bool:
curr = self.root
for char in prefix:
if char not in curr.children:
return False
curr = curr.children[char]
return True

Java

class TrieNode {
TrieNode[] children;
boolean isEnd;
public TrieNode() {
children = new TrieNode[26];
isEnd = false;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (curr.children[idx] == null) {
curr.children[idx] = new TrieNode();
}
curr = curr.children[idx];
}
curr.isEnd = true;
}
public boolean search(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (curr.children[idx] == null) return false;
curr = curr.children[idx];
}
return curr.isEnd;
}
public boolean startsWith(String prefix) {
TrieNode curr = root;
for (char c : prefix.toCharArray()) {
int idx = c - 'a';
if (curr.children[idx] == null) return false;
curr = curr.children[idx];
}
return true;
}
}

🌍 Real-World Analogy

Dictionary / Phonebook:

Looking up a word in a physical dictionary. You look for 'A', then 'Ap', then 'App', then 'Appl', then 'Apple'. If you can't find the next page, the word doesn't exist.

🎯 Summary

✅ Shared Prefixes: Tries save space when many words share prefixes (e.g., "star", "start", "starting").