Tries (Prefix Trees)

🎯 Explain Like I'm 5...

Imagine you have a magical word tree where each letter is a branch! When you spell words, you follow the branches like climbing a tree.

🌳 Word Tree - How It Works:

• Start at the root (the trunk of the tree) 🌲
• For 'CAT': Follow branch 'C' → then 'A' → then 'T' → mark T as 'end of word!' ⭐
• For 'CAR': Follow branch 'C' → then 'A' → then 'R' → mark R as 'end of word!' ⭐

See? 'CA' is shared! Both words use the same branches until they split! Super clever! 🎯

🔍 Finding Words That Start the Same:

Want all words starting with 'CA'? Just follow 'C' → 'A' and explore all branches from there!

• Type 'CA...' → Tree shows: CAT, CAR, CAN, CAKE
• Just like when you type on your phone and it suggests words!
• The tree remembers all the words you put in it!

🚀 Why Are Tries Useful?

• Finding words is super fast - just follow the letters!
• Perfect for autocomplete - like when your phone suggests words!
• Saves space when words share the same beginning!

🔧 Basic Operations

Trie Node Structure

TrieNode.java

java

// Trie Node - represents each node in the word tree
class TrieNode {
    // Children array - one slot for each letter (a-z = 26 letters)
    TrieNode[] children;
    // Flag to mark if this node represents end of a word
    boolean isEndOfWord;
    // Constructor - initialize the node
    public TrieNode() {
        children = new TrieNode[26];  // 26 letters in alphabet
        isEndOfWord = false;           // Initially not end of word
    }
}
// Alternative: Using HashMap for more flexibility (supports any character)
class TrieNodeWithMap {
    HashMap<Character, TrieNode> children;
    boolean isEndOfWord;
    public TrieNodeWithMap() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

Insert Operation - Adding Words to the Tree

TrieInsert.java

java

class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    // Insert a word into the trie
    // Time: O(m) where m is length of word
    // Space: O(m) in worst case for new word
    public void insert(String word) {
        TrieNode current = root;  // Start from root
        // Process each character in the word
        for (char ch : word.toCharArray()) {
            // Convert char to index: 'a' -> 0, 'b' -> 1, etc.
            int index = ch - 'a';
            // If path doesn't exist, create new node
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            // Move to the child node
            current = current.children[index];
        }
        // Mark the last node as end of word
        current.isEndOfWord = true;
    }
    public static void main(String[] args) {
        Trie trie = new Trie();
        // Insert words into the trie
        trie.insert("cat");
        trie.insert("car");
        trie.insert("card");
        trie.insert("dog");
        System.out.println("Words inserted into trie!");
        // Tree structure:
        //        root
        //       /    \
        //      c      d
        //      |      |
        //      a      o
        //     / \     |
        //    t   r     g*
        //    *   |
        //        d*
    }
}

Search Operation - Finding Complete Words

TrieSearch.java

java

class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    // Search for a complete word in trie
    // Time: O(m) where m is length of word
    // Space: O(1) - only uses pointers
    public boolean search(String word) {
        TrieNode current = root;
        // Follow the path for each character
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            // If path doesn't exist, word is not in trie
            if (current.children[index] == null) {
                return false;
            }
            // Move to next node
            current = current.children[index];
        }
        // Check if we're at end of a word (not just a prefix)
        return current.isEndOfWord;
    }
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        trie.insert("car");
        System.out.println(trie.search("cat"));   // true - complete word
        System.out.println(trie.search("car"));   // true - complete word
        System.out.println(trie.search("ca"));    // false - just prefix
        System.out.println(trie.search("card"));  // false - not inserted
        System.out.println(trie.search("dog"));   // false - not inserted
    }
}

Prefix Search - Finding Words That Start With...

TrieStartsWith.java

java

class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    // Check if there are any words with given prefix
    // Time: O(m) where m is length of prefix
    // Space: O(1)
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        // Follow the path for each character
        for (char ch : prefix.toCharArray()) {
            int index = ch - 'a';
            // If path doesn't exist, no words with this prefix
            if (current.children[index] == null) {
                return false;
            }
            // Move to next node
            current = current.children[index];
        }
        // If we completed the path, prefix exists
        // (doesn't matter if it's end of word or not)
        return true;
    }
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("application");
        trie.insert("app");
        System.out.println(trie.startsWith("app"));    // true - "app", "apple", "application"
        System.out.println(trie.startsWith("appl"));   // true - "apple", "application"
        System.out.println(trie.startsWith("ban"));    // false - no words start with "ban"
        System.out.println(trie.search("app"));        // true - complete word
        System.out.println(trie.search("appl"));       // false - not complete word
    }
}

📝 Advanced Trie Operations

Delete Operation

TrieDelete.java

java

class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    // Delete a word from trie
    // Returns true if node should be deleted
    private boolean deleteHelper(TrieNode current, String word, int index) {
        // Base case: reached end of word
        if (index == word.length()) {
            // If not end of word, word doesn't exist
            if (!current.isEndOfWord) {
                return false;
            }
            // Unmark as end of word
            current.isEndOfWord = false;
            // If node has no children, can be deleted
            return hasNoChildren(current);
        }
        char ch = word.charAt(index);
        int childIndex = ch - 'a';
        TrieNode child = current.children[childIndex];
        // If path doesn't exist, word not in trie
        if (child == null) {
            return false;
        }
        // Recursively delete from child
        boolean shouldDeleteChild = deleteHelper(child, word, index + 1);
        // If child should be deleted, remove it
        if (shouldDeleteChild) {
            current.children[childIndex] = null;
            // If current node has no other children and is not end of word, delete it too
            return hasNoChildren(current) && !current.isEndOfWord;
        }
        return false;
    }
    // Check if node has any children
    private boolean hasNoChildren(TrieNode node) {
        for (TrieNode child : node.children) {
            if (child != null) {
                return false;
            }
        }
        return true;
    }
    public void delete(String word) {
        deleteHelper(root, word, 0);
    }
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        trie.insert("car");
        trie.insert("card");
        System.out.println("Before delete:");
        System.out.println(trie.search("car"));   // true
        System.out.println(trie.search("card"));  // true
        trie.delete("car");
        System.out.println("\nAfter deleting 'car':");
        System.out.println(trie.search("car"));   // false
        System.out.println(trie.search("card"));  // true - still exists!
    }
}

Get All Words from Trie

TrieGetAllWords.java

java

import java.util.ArrayList;
import java.util.List;
class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    // Get all words in the trie
    public List<String> getAllWords() {
        List<String> words = new ArrayList<>();
        collectWords(root, new StringBuilder(), words);
        return words;
    }
    // Recursively collect all words using DFS
    private void collectWords(TrieNode node, StringBuilder currentWord, List<String> words) {
        // If this node marks end of word, add to list
        if (node.isEndOfWord) {
            words.add(currentWord.toString());
        }
        // Explore all children (a-z)
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                // Add current character
                char ch = (char) ('a' + i);
                currentWord.append(ch);
                // Recursively explore this branch
                collectWords(node.children[i], currentWord, words);
                // Backtrack - remove character
                currentWord.deleteCharAt(currentWord.length() - 1);
            }
        }
    }
    // Get all words with given prefix
    public List<String> getWordsWithPrefix(String prefix) {
        List<String> words = new ArrayList<>();
        TrieNode current = root;
        // Navigate to prefix
        for (char ch : prefix.toCharArray()) {
            int index = ch - 'a';
            if (current.children[index] == null) {
                return words;  // No words with this prefix
            }
            current = current.children[index];
        }
        // Collect all words from this point
        collectWords(current, new StringBuilder(prefix), words);
        return words;
    }
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        trie.insert("car");
        trie.insert("card");
        trie.insert("dog");
        trie.insert("door");
        System.out.println("All words: " + trie.getAllWords());
        // Output: [car, card, cat, dog, door]
        System.out.println("Words with prefix 'ca': " + trie.getWordsWithPrefix("ca"));
        // Output: [car, card, cat]
        System.out.println("Words with prefix 'do': " + trie.getWordsWithPrefix("do"));
        // Output: [dog, door]
    }
}

💡 Common Problems & Solutions

Problem 1: Implement Trie (Prefix Tree)

Build a complete Trie data structure with insert, search, and startsWith operations!

💡 How it works (Trie Data Structure):

The Challenge: Implement a trie with insert, search, and prefix search operations

The Solution (Node + Children Array):

1. Each TrieNode has:

• Array of 26 children (one for each letter a-z)

• Boolean flag isEndOfWord

2. Insert: Follow/create path for each letter

3. Search: Follow path, check isEndOfWord at end

4. StartsWith: Follow path, return true if path exists

Key Insight: Words share common prefixes in the tree structure

Visual Example:

Insert 'app', 'apple', 'application':

root
|
a
|
p
|
p* (end of 'app')
|
l
/ \
i e* (end of 'apple')
|
c
|
a
|
t
|
i
|
o
|
n* (end of 'application')

search('app') → true (isEndOfWord at 'p')
search('appl') → false (not isEndOfWord at 'l')
startsWith('app') → true (path exists)

⏱️ Time Complexity: O(m) for all operations, m = word length

💾 Space Complexity: O(alphabet_size * n * m) worst case

CompleteTrie.java

java

// Complete Trie Implementation
// LeetCode 208 - Implement Trie (Prefix Tree)
class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;
    public TrieNode() {
        children = new TrieNode[26];
        isEndOfWord = false;
    }
}
class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    // Insert word into trie - O(m) time, O(m) space
    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }
    // Search for complete word - O(m) time, O(1) space
    public boolean search(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return current.isEndOfWord;
    }
    // Check if prefix exists - O(m) time, O(1) space
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char ch : prefix.toCharArray()) {
            int index = ch - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return true;
    }
}
// Usage
public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));     // true
        System.out.println(trie.search("app"));       // false
        System.out.println(trie.startsWith("app"));   // true
        trie.insert("app");
        System.out.println(trie.search("app"));       // true
    }
}

Problem 2: Word Search II

Find all words from a dictionary that exist in a 2D board - uses Trie for efficient search!

💡 How it works (Trie + DFS Backtracking):

The Challenge: Find ALL words from dictionary in 2D board (not just one word)

The Solution (Trie Pruning):

1. Build trie from all dictionary words

2. DFS from each board cell:

• Follow trie paths as you explore

• If trie path doesn't exist, prune (stop exploring)

• If reach word end in trie, add to results

3. Mark cells as visited during DFS

Why Trie is Smart: Prunes impossible paths early - don't explore if no words start with this prefix!

Visual Example:

Board: o a a n
e t a e
i h k r
i f l v

Dictionary: ['oath', 'pea', 'eat', 'rain']

Build Trie from dictionary:
o → a → t → h*
p → e → a*
e → a → t*
r → a → i → n*

DFS from (0,0) 'o':
'o' in trie → continue
Try neighbors: 'a', 'e'
'o'→'a' in trie → continue
'o'→'a'→'t' in trie → continue
'o'→'a'→'t'→'h' found 'oath'! ✓

Without trie: Try every path (exponential!)
With trie: Prune paths that don't match dictionary

⏱️ Time Complexity: O(rows * cols * 4^L) where L = max word length

💾 Space Complexity: O(n * m) for trie, n = number of words

WordSearch2.java

java

import java.util.*;
// LeetCode 212 - Word Search II
// Find all words from dictionary that exist in 2D board
class WordSearch2 {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;  // Store word at end node
    }
    // Build trie from dictionary words
    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode current = root;
            for (char ch : word.toCharArray()) {
                int index = ch - 'a';
                if (current.children[index] == null) {
                    current.children[index] = new TrieNode();
                }
                current = current.children[index];
            }
            current.word = word;  // Mark end with complete word
        }
        return root;
    }
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        TrieNode root = buildTrie(words);
        // Try starting from each cell
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, result);
            }
        }
        return result;
    }
    private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
        // Boundary checks
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return;
        }
        char ch = board[i][j];
        if (ch == '#' || node.children[ch - 'a'] == null) {
            return;
        }
        node = node.children[ch - 'a'];
        // Found a word!
        if (node.word != null) {
            result.add(node.word);
            node.word = null;  // Avoid duplicates
        }
        // Mark as visited
        board[i][j] = '#';
        // Explore all 4 directions
        dfs(board, i + 1, j, node, result);
        dfs(board, i - 1, j, node, result);
        dfs(board, i, j + 1, node, result);
        dfs(board, i, j - 1, node, result);
        // Restore cell
        board[i][j] = ch;
    }
    public static void main(String[] args) {
        WordSearch2 ws = new WordSearch2();
        char[][] board = {
            {'o','a','a','n'},
            {'e','t','a','e'},
            {'i','h','k','r'},
            {'i','f','l','v'}
        };
        String[] words = {"oath","pea","eat","rain"};
        List<String> found = ws.findWords(board, words);
        System.out.println("Found words: " + found);
        // Output: [oath, eat]
    }
}

Problem 3: Autocomplete System

Design an autocomplete system that suggests words based on prefix - like search engines!

💡 How it works (Trie with Frequency Map):

The Challenge: Return top 3 most frequent sentences for each prefix typed

The Solution (Store Sentences at Each Node):

1. Each TrieNode stores:

→ Map of sentence → frequency for all sentences passing through

2. When character typed:

• Move to child node

• Get all sentences at that node

• Sort by frequency (then lexicographically)

• Return top 3

3. When '#' typed: save sentence and reset

Optimization: Store full sentences at each node for quick retrieval

Visual Example:

Sentences: ['i love you': 5, 'island': 3, 'i love leetcode': 2]

Trie stores sentences at each node:
i → {'i love you': 5, 'island': 3, 'i love leetcode': 2}
i → ' ' → {'i love you': 5, 'i love leetcode': 2}
i → s → {'island': 3}

User types 'i':
Node 'i' has sentences:
1. 'i love you' (5 times)
2. 'island' (3 times)
3. 'i love leetcode' (2 times)
Return top 3: ['i love you', 'island', 'i love leetcode']

User types ' ' (now 'i '):
Node 'i' → ' ' has sentences:
1. 'i love you' (5 times)
2. 'i love leetcode' (2 times)
Return: ['i love you', 'i love leetcode']

⏱️ Time Complexity: O(p + m log m) per input, p = prefix, m = matching sentences

💾 Space Complexity: O(n * k^2) where n = sentences, k = avg length

AutocompleteSystem.java

java

import java.util.*;
// LeetCode 642 - Design Search Autocomplete System
class AutocompleteSystem {
    class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        Map<String, Integer> sentences = new HashMap<>();  // sentence -> frequency
    }
    private TrieNode root;
    private TrieNode current;
    private StringBuilder currentInput;
    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new TrieNode();
        current = root;
        currentInput = new StringBuilder();
        // Build trie with initial sentences
        for (int i = 0; i < sentences.length; i++) {
            addSentence(sentences[i], times[i]);
        }
    }
    private void addSentence(String sentence, int count) {
        TrieNode node = root;
        // Add sentence to each node along the path
        for (char ch : sentence.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                node.children.put(ch, new TrieNode());
            }
            node = node.children.get(ch);
            node.sentences.put(sentence, node.sentences.getOrDefault(sentence, 0) + count);
        }
    }
    public List<String> input(char c) {
        if (c == '#') {
            // Save current sentence
            addSentence(currentInput.toString(), 1);
            // Reset for next input
            currentInput = new StringBuilder();
            current = root;
            return new ArrayList<>();
        }
        currentInput.append(c);
        if (current != null && current.children.containsKey(c)) {
            current = current.children.get(c);
        } else {
            current = null;
            return new ArrayList<>();
        }
        // Get top 3 hot sentences
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
            (a, b) -> a.getValue() == b.getValue() ?
                      a.getKey().compareTo(b.getKey()) :
                      b.getValue() - a.getValue()
        );
        pq.addAll(current.sentences.entrySet());
        List<String> result = new ArrayList<>();
        for (int i = 0; i < 3 && !pq.isEmpty(); i++) {
            result.add(pq.poll().getKey());
        }
        return result;
    }
    public static void main(String[] args) {
        String[] sentences = {"i love you", "island", "iroman", "i love leetcode"};
        int[] times = {5, 3, 2, 2};
        AutocompleteSystem system = new AutocompleteSystem(sentences, times);
        System.out.println(system.input('i'));  // ["i love you", "island", "i love leetcode"]
        System.out.println(system.input(' '));  // ["i love you", "i love leetcode"]
        System.out.println(system.input('a'));  // []
        System.out.println(system.input('#'));  // Save "i a"
    }
}

Problem 4: Longest Word in Dictionary

Find the longest word that can be built one character at a time!

💡 How it works (Trie + DFS Validation):

The Challenge: Find longest word buildable one character at a time

The Solution (Only Traverse Complete Words):

1. Build trie from all words

2. DFS from root with constraint:

→ ONLY follow paths where EVERY node is a complete word

3. Track longest word found during DFS

Example: Words: [w, wo, wor, worl, world] → world is buildable step by step

Why It Works: If every prefix is a word, the full word is buildable one char at a time

Visual Example:

Words: ['w', 'wo', 'wor', 'worl', 'world']

Build trie:
w* (word)
└─ o* (word)
└─ r* (word)
└─ l* (word)
└─ d* (word)

DFS with constraint (only traverse complete words):
Start at 'w' → is word? YES ✓
Go to 'o' → is word? YES ✓
Go to 'r' → is word? YES ✓
Go to 'l' → is word? YES ✓
Go to 'd' → is word? YES ✓
Result: 'world' (length 5) ✓

Counter-example: ['w', 'world'] (missing 'wo', 'wor', 'worl')
'w' is word, but 'wo' is NOT a word → STOP
Can't reach 'world' → Result: 'w' (length 1)

⏱️ Time Complexity: O(sum of all word lengths) for building + DFS

💾 Space Complexity: O(sum of all word lengths) for trie

LongestWord.java

java

import java.util.*;
// LeetCode 720 - Longest Word in Dictionary
// Find longest word that can be built one character at a time
class LongestWord {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;
    }
    public String longestWord(String[] words) {
        // Build trie
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode current = root;
            for (char ch : word.toCharArray()) {
                int index = ch - 'a';
                if (current.children[index] == null) {
                    current.children[index] = new TrieNode();
                }
                current = current.children[index];
            }
            current.word = word;
        }
        // DFS to find longest word that can be built char by char
        String[] longest = {""};
        dfs(root, longest);
        return longest[0];
    }
    private void dfs(TrieNode node, String[] longest) {
        for (int i = 0; i < 26; i++) {
            // Only continue if child exists AND is a complete word
            if (node.children[i] != null && node.children[i].word != null) {
                TrieNode child = node.children[i];
                // Update longest if this word is longer (or same length but lexicographically smaller)
                if (child.word.length() > longest[0].length() ||
                    (child.word.length() == longest[0].length() &&
                     child.word.compareTo(longest[0]) < 0)) {
                    longest[0] = child.word;
                }
                dfs(child, longest);
            }
        }
    }
    public static void main(String[] args) {
        LongestWord lw = new LongestWord();
        // Example 1
        String[] words1 = {"w","wo","wor","worl","world"};
        System.out.println(lw.longestWord(words1));  // "world"
        // Example 2
        String[] words2 = {"a","banana","app","appl","ap","apply","apple"};
        System.out.println(lw.longestWord(words2));  // "apple"
        // "apply" is also valid but "apple" is lexicographically smaller
        // Example 3
        String[] words3 = {"yo","ew","fc","zrc","yodn","fcm","qm","qmo","fcmz","z","ewq","yod","ewqz","y"};
        System.out.println(lw.longestWord(words3));  // "yodn"
    }
}

🔑 Key Points to Remember

1️⃣Each node stores children (next letters) and a boolean flag for word ending
2️⃣Insert/Search/StartsWith are all O(m) where m is word length - very fast!
3️⃣Space efficient for common prefixes - 'cat' and 'car' share 'ca'
4️⃣Perfect for dictionary operations, autocomplete, and spell checking
5️⃣Can use array[26] for lowercase letters or HashMap for any characters

💪 Practice Problems

• Implement Trie (Insert, Search, StartsWith)
• Word Search II (find words in 2D board)
• Design Search Autocomplete System
• Replace Words (replace suffixes with roots)
• Longest Word in Dictionary
• Add and Search Word (with wildcard '.')
• Maximum XOR of Two Numbers in Array (using binary trie)