Trie (Prefix Tree)

Generated on 2025-07-10 02:04:24 Algorithm Cheatsheet for Technical Interviews

---

Trie (Prefix Tree) Cheatsheet

1. Quick Overview

• What it is: A tree-like data structure used for efficient retrieval of keys in a dataset, most commonly strings. Each node represents a prefix, and edges represent characters.
• When to use:
  • Prefix-based search (e.g., autocomplete, spell checking).
  • Storing a large vocabulary of words.
  • Longest Prefix Matching.
  • IP Routing (using bitwise Tries).
  • Replacing hash tables when collision handling is costly and the keys are strings.

2. Time & Space Complexity

Operation	Time Complexity	Space Complexity
Insertion	O(m)	O(m * k)
Search	O(m)	O(1)
Prefix Search	O(m)	O(1)
Deletion	O(m)	O(1)

• m: Length of the key (string).
• k: Size of the alphabet (e.g., 26 for lowercase English letters).
• Note: Space complexity can be significant, especially for large alphabets.

3. Implementation

Python:

class TrieNode:
    def __init__(self):
        self.children = {}  # Dictionary to store child nodes
        self.is_end_of_word = False  # Flag to indicate end of a word

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """Inserts a word into the trie."""
        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
        # Time Complexity: O(m), m = length of the word

    def search(self, word: str) -> bool:
        """Returns if the word is in the trie."""
        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
        # Time Complexity: O(m), m = length of the word

    def startsWith(self, prefix: str) -> bool:
        """Returns if there is any word in the trie that starts with the given prefix."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True
        # Time Complexity: O(m), m = length of the prefix

Java:

class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[26]; // Assuming lowercase English letters
        isEndOfWord = false;
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
        // Time Complexity: O(m), m = length of the word
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
        // Time Complexity: O(m), m = length of the word
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return true;
        // Time Complexity: O(m), m = length of the prefix
    }
}

C++:

#include <iostream>
#include <vector>

using namespace std;

class TrieNode {
public:
    vector<TrieNode*> children;
    bool isEndOfWord;

    TrieNode() {
        children.resize(26, nullptr); // Assuming lowercase English letters
        isEndOfWord = false;
    }
};

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] == nullptr) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEndOfWord = true;
        // Time Complexity: O(m), m = length of the word
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return node->isEndOfWord;
        // Time Complexity: O(m), m = length of the word
    }

    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return true;
        // Time Complexity: O(m), m = length of the prefix
    }
};

4. Common Patterns

• Autocomplete: Use startsWith to find all words with a given prefix, then perform a Depth-First Search (DFS) to collect all words under that prefix.
• Spell Checking: Search for words in the trie. If a word is not found, suggest words with similar prefixes.
• Longest Common Prefix: Traverse the trie until a node has more than one child or is a terminal node.
• IP Routing: Use a bitwise Trie to store IP addresses and their corresponding routes.

5. Pro Tips

• Alphabet Size: Choose the appropriate alphabet size based on the input data (e.g., 26 for lowercase English letters, 128 for ASCII characters, 256 for extended ASCII).
• Node Structure: The children can be implemented as an array, a hash map, or a linked list, depending on the alphabet size and insertion/search frequency. Arrays are generally faster for small alphabets, while hash maps offer better space efficiency for large alphabets.
• Memory Optimization:
  • Radix Trie (Patricia Trie): Compress paths with single children.
  • DAWG (Directed Acyclic Word Graph): Merge common suffixes.
• Deletion: Implement deletion carefully to avoid memory leaks. A node should only be deleted if it’s not part of any other word.
• Case Sensitivity: Be aware of case sensitivity requirements. Convert all input to lowercase or uppercase if necessary.

6. Practice Problems

1. LeetCode 208. Implement Trie (Prefix Tree): Implement the Trie class with insert, search, and startsWith methods.
2. LeetCode 211. Design Add and Search Words Data Structure: Design a data structure that supports adding new words and searching for a word. The search method can search literal words or words with the . character (representing any single character).
3. LeetCode 421. Maximum XOR of Two Numbers in an Array: Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n. (Hint: Use a bitwise Trie).

7. Templates

Python:

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 True

Java:

class TrieNode {
    TrieNode[] children;
    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 c : word.toCharArray()) {
            int index = c - '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 c : word.toCharArray()) {
            int index = c - '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 c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return true;
    }
}

C++:

#include <iostream>
#include <vector>

using namespace std;

class TrieNode {
public:
    vector<TrieNode*> children;
    bool isEndOfWord;

    TrieNode() {
        children.resize(26, nullptr);
        isEndOfWord = false;
    }
};

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] == nullptr) {
                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] == nullptr) {
                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] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return true;
    }
};