Construct a trie from scratch
Problem Statement
Construct a Trie (prefix tree) data structure from scratch that supports the following operations:
- insert(word): Insert a word into the trie.
- search(word): Return true if the word exists in the trie.
- startsWith(prefix): Return true if any word in the trie starts with the given prefix.
Example:
Input:
insert("apple")
insert("app")
search("apple") → true
search("app") → true
search("ap") → false
startsWith("ap") → true
Noob-Friendly Explanation
Imagine you have a dictionary book, but instead of flipping through every single page to find a word, you organize the words in a clever way.
Think of a tree where each branch is a letter. To store the word "cat", you go from the root → c → a → t. To store "car", you go root → c → a → r. Notice how "cat" and "car" share the "c" and "a" branches! That's the magic of a Trie — common prefixes share the same path, saving space and making lookups super fast.
It's like a phone's autocomplete: when you type "ap", it quickly finds "apple", "app", "application" because they all live on the same branch starting with "a" → "p".
Approach 1: Brute Force (Using a List of Strings)
Intuition
The simplest approach is to just store all words in a list. For search, loop through the list. For prefix search, check if any word starts with the prefix.
Algorithm
- Maintain an ArrayList of strings
- For insert, add the word to the list
- For search, iterate and compare each word
- For startsWith, iterate and check prefix of each word
import java.util.*;
class TrieBruteForce {
private List<String> words;
public TrieBruteForce() {
words = new ArrayList<>();
}
public void insert(String word) {
if (!words.contains(word)) {
words.add(word);
}
}
public boolean search(String word) {
for (String w : words) {
if (w.equals(word)) {
return true;
}
}
return false;
}
public boolean startsWith(String prefix) {
for (String w : words) {
if (w.startsWith(prefix)) {
return true;
}
}
return false;
}
public static void main(String[] args) {
TrieBruteForce trie = new TrieBruteForce();
trie.insert("apple");
trie.insert("app");
System.out.println(trie.search("apple")); // true
System.out.println(trie.search("app")); // true
System.out.println(trie.search("ap")); // false
System.out.println(trie.startsWith("ap")); // true
}
}Complexity Analysis
- Time Complexity: O(N * L) — For each search/startsWith, we scan all N words, each up to length L
- Space Complexity: O(N * L) — Storing all N words of average length L
Approach 2: Optimal (Trie Data Structure)
Intuition
Build an actual tree where each node has up to 26 children (one for each letter). Each path from root to a node represents a prefix. We mark certain nodes as "end of word" to distinguish complete words from just prefixes.
Algorithm
- Create a TrieNode class with an array of 26 children and a boolean
isEndOfWord - Insert: Walk through each character of the word, creating nodes if they don't exist, and mark the last node
- Search: Walk through each character; if any node is missing, return false. Check
isEndOfWordat the end - StartsWith: Same as search but don't check
isEndOfWord
class Trie {
static class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26];
isEndOfWord = false;
}
}
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (current.children[index] == null) {
return false;
}
current = current.children[index];
}
return current.isEndOfWord;
}
public boolean startsWith(String prefix) {
TrieNode current = root;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (current.children[index] == null) {
return false;
}
current = current.children[index];
}
return true;
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("apple");
trie.insert("app");
System.out.println(trie.search("apple")); // true
System.out.println(trie.search("app")); // true
System.out.println(trie.search("ap")); // false
System.out.println(trie.startsWith("ap")); // true
}
}Complexity Analysis
- Time Complexity: O(N * L) — Each insert/search/startsWith takes O(L) for a word of length L, and we do it for N words
- Space Complexity: O(N * L * 26) — In the worst case, each character of each word creates a new node with 26 slots
Key Takeaways
- Trie = Prefix Tree: It stores strings character-by-character in a tree
- Shared Prefixes: Words with common prefixes share the same path, saving space
- O(L) Lookups: Search time depends only on word length, not the number of words stored
- isEndOfWord: Crucial to distinguish complete words from prefixes
- Use Cases: Autocomplete, spell checkers, IP routing, dictionary lookups