Implement Trie (Prefix Tree)

📋

Problem

Imagine you are building a search autocomplete feature that suggests words as you type. Efficiently storing and querying prefixes is key to a smooth user experience.

Design a data structure that supports the following operations: insert a word, search for a word, and check if any word starts with a given prefix. Implement the Trie class with methods insert(word), search(word), and startsWith(prefix).

1 ≤ total number of calls to insert, search, and startsWith ≤ 10^5All inputs consist of lowercase English letters a-z1 ≤ length of word or prefix ≤ 2000

Edge cases: search for empty string → false (empty strings are not inserted)startsWith empty string → true (every word starts with empty prefix)insert duplicate words → no error, trie structure remains valid

</>

IDE

def insert(self, word: str) -> None / def search(self, word: str) -> bool / def startsWith(self, prefix: str) -> boolpublic void insert(String word) / public boolean search(String word) / public boolean startsWith(String prefix)void insert(string word) / bool search(string word) / bool startsWith(string prefix)function insert(word) / function search(word) / function startsWith(prefix)

class Trie:
    def __init__(self):
        # Write your solution here
        pass
    def insert(self, word: str) -> None:
        pass
    def search(self, word: str) -> bool:
        pass
    def startsWith(self, prefix: str) -> bool:
        pass

class Trie {
    public Trie() {
        // Write your solution here
    }
    public void insert(String word) {
        // Write your solution here
    }
    public boolean search(String word) {
        // Write your solution here
        return false;
    }
    public boolean startsWith(String prefix) {
        // Write your solution here
        return false;
    }
}

#include <string>
using namespace std;

class Trie {
public:
    Trie() {
        // Write your solution here
    }
    void insert(string word) {
        // Write your solution here
    }
    bool search(string word) {
        // Write your solution here
        return false;
    }
    bool startsWith(string prefix) {
        // Write your solution here
        return false;
    }
};

class Trie {
    constructor() {
        // Write your solution here
    }
    insert(word) {
        // Write your solution here
    }
    search(word) {
        // Write your solution here
        return false;
    }
    startsWith(prefix) {
        // Write your solution here
        return false;
    }
}

Common Bugs to Avoid

Wrong: search returns true for prefixes that are not inserted wordssearch method returns true if prefix path exists without checking is_end flag✅ In search, return true only if is_end flag is true at the last node of the word

Wrong: startsWith returns false for empty string prefixstartsWith does not handle empty string input explicitly✅ Add explicit check: if prefix is empty string, return true immediately

Wrong: search returns true for empty stringsearch does not handle empty string input explicitly and returns true by default✅ Add explicit check: if word is empty string, return false

Wrong: duplicate insert causes trie corruption or errorsinsert method creates new nodes without checking existing children, or resets is_end incorrectly✅ Traverse existing nodes if present and set is_end flag at last node without duplicating nodes

Wrong: TLE on large inputUsing brute force list scanning approach with O(n*m) per query✅ Implement trie with node children and is_end flags to achieve O(m) per query complexity

✓

Test Cases

Focus on handling empty inputs and minimal cases correctly before moving on.

Make sure your search and startsWith methods correctly distinguish words from prefixes.

Optimize your data structure to avoid scanning all inserted words on each query.

t1_01basic

Input{"calls":[{"method":"insert","args":["apple"]},{"method":"search","args":["apple"]},{"method":"search","args":["app"]},{"method":"startsWith","args":["app"]},{"method":"insert","args":["app"]},{"method":"search","args":["app"]}]}

Expected[null,true,false,true,null,true]

⏱ Performance - must finish in 2000ms

After inserting 'apple', searching 'apple' returns true. Searching 'app' returns false because 'app' was not inserted as a word. startsWith('app') returns true because 'apple' starts with 'app'. After inserting 'app', searching 'app' returns true.

💡 Think about how to represent each character as a node in a tree structure.

💡 Use a map or array to store children nodes and a flag to mark word endings.

💡 Implement insert by creating nodes for each character; search and startsWith traverse nodes accordingly.

Why it failed: Basic case failed - likely your search or startsWith does not correctly check the is_end flag or children nodes. Fix by ensuring search returns true only if is_end is true at last node, and startsWith returns true if prefix path exists.

✓ Core trie insert, search, and startsWith logic implemented correctly.

t1_02basic

Input{"calls":[{"method":"insert","args":["banana"]},{"method":"search","args":["ban"]},{"method":"startsWith","args":["ban"]},{"method":"insert","args":["band"]},{"method":"search","args":["band"]},{"method":"search","args":["banana"]}]}

Expected[null,false,true,null,true,true]

⏱ Performance - must finish in 2000ms

Inserting 'banana' then searching 'ban' returns false because 'ban' is a prefix but not a word. startsWith('ban') returns true. After inserting 'band', searching 'band' returns true. Searching 'banana' returns true as well.

💡 Remember that search must confirm the word ends at the last character node.

💡 startsWith only requires the prefix path to exist, not the is_end flag.

💡 Check that insert correctly marks the end of each inserted word.

Why it failed: Search incorrectly returns true for prefixes that are not words or startsWith returns false when prefix exists. Fix by distinguishing is_end flag usage in search vs startsWith.

✓ Correctly distinguishes between word search and prefix search.

t2_01edge

Input{"calls":[{"method":"search","args":[""]},{"method":"startsWith","args":[""]}]}

Expected[false,true]

⏱ Performance - must finish in 2000ms

Searching for empty string returns false because empty strings are not inserted. startsWith empty string returns true because every word starts with empty prefix.

💡 Consider how your code handles empty strings in search and startsWith.

💡 Empty prefix should always return true for startsWith, but empty word search should return false.

💡 Add explicit checks for empty string inputs in search and startsWith methods.

Why it failed: Empty string search incorrectly returns true or empty prefix startsWith returns false. Fix by adding explicit checks: search('') returns false; startsWith('') returns true.

✓ Correct handling of empty string inputs in search and startsWith.

t2_02edge

Input{"calls":[{"method":"insert","args":["a"]},{"method":"search","args":["a"]},{"method":"startsWith","args":["a"]}]}

Expected[null,true,true]

⏱ Performance - must finish in 2000ms

Single character word inserted and searched returns true; startsWith with that character returns true.

💡 Test your trie with the smallest possible word length.

💡 Ensure is_end flag is set correctly even for single character words.

💡 Verify that children nodes are created properly for single characters.

Why it failed: Single element insert/search fails due to missing is_end flag or children node creation. Fix by setting is_end true at last node even if only one character.

✓ Correctly handles single character words.

t2_03edge

Input{"calls":[{"method":"insert","args":["test"]},{"method":"insert","args":["test"]},{"method":"search","args":["test"]}]}

Expected[null,null,true]

⏱ Performance - must finish in 2000ms

Inserting duplicate words does not cause error; searching returns true.

💡 Consider how your insert handles duplicate words.

💡 Ensure inserting the same word twice does not corrupt the trie structure.

💡 Insert should be idempotent for the same word.

Why it failed: Duplicate insert corrupts trie or causes errors. Fix by allowing insert to traverse existing nodes and set is_end flag without duplication.

✓ Duplicate inserts handled gracefully.

t3_01corner

Input{"calls":[{"method":"insert","args":["abc"]},{"method":"insert","args":["abcd"]},{"method":"search","args":["abc"]},{"method":"search","args":["abcd"]},{"method":"search","args":["ab"]}]}

Expected[null,null,true,true,false]

⏱ Performance - must finish in 2000ms

Tests that search distinguishes between prefix and full word. 'abc' and 'abcd' inserted; searching 'ab' returns false.

💡 Check that search returns true only if is_end flag is set at last node.

💡 Avoid returning true just because prefix path exists.

💡 Verify is_end flag is correctly set for each inserted word.

Why it failed: Search returns true for prefixes that are not words. Fix by checking is_end flag at last node in search method.

✓ Search correctly distinguishes words from prefixes.

t3_02corner

Input{"calls":[{"method":"insert","args":["a"]},{"method":"insert","args":["ab"]},{"method":"startsWith","args":["a"]},{"method":"startsWith","args":["ab"]},{"method":"startsWith","args":["abc"]}]}

Expected[null,null,true,true,false]

⏱ Performance - must finish in 2000ms

Tests startsWith correctness: 'a' and 'ab' prefixes exist, 'abc' does not.

💡 startsWith should return true if prefix path exists regardless of is_end flag.

💡 Check traversal logic carefully for startsWith.

💡 Return false only if prefix path breaks at any character.

Why it failed: startsWith returns false for existing prefixes or true for non-existing prefixes. Fix by correctly traversing prefix path and returning true if path exists.

✓ startsWith correctly identifies existing prefixes.

t3_03corner

Input{"calls":[{"method":"insert","args":["abc"]},{"method":"search","args":["abcd"]},{"method":"startsWith","args":["abcd"]}]}

Expected[null,false,false]

⏱ Performance - must finish in 2000ms

Tests that search and startsWith return false for prefixes longer than any inserted word.

💡 Check boundary conditions when prefix or word is longer than any inserted word.

💡 Ensure traversal stops correctly when child node missing.

💡 Return false immediately if path breaks.

Why it failed: search or startsWith incorrectly returns true for non-existent longer prefixes. Fix by stopping traversal when child node missing and returning false.

✓ Correctly handles non-existent longer prefixes.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Test with 100000 calls to insert/search/startsWith to verify O(m) complexity per operation completes within 2 seconds.

💡 Naive list-based solutions will time out due to O(n*m) per query.

💡 Use trie data structure with O(m) insert/search/startsWith complexity.

💡 Avoid repeated string scans; use node children maps or arrays.

Why it failed: TLE due to using brute force list scanning approach. Fix by implementing trie with node children and is_end flags for O(m) operations.

✓ Efficient trie implementation with O(m) per operation confirmed.

Practice

1. Given a string text and a list of words, you need to find all pairs of indices [i, j] such that the substring text[i:j+1] is in the list of words. Which approach guarantees an optimal solution in terms of time complexity when the list of words is large and words have varying lengths?

easy

A. Build a trie from the list of words and perform a DFS from each index in the text to find matching substrings.

B. Use dynamic programming to store whether substrings are in the word list and build results bottom-up.

C. Use a brute force nested loop to check every substring against the list of words directly.

D. Sort the list of words and use binary search to check each substring generated from the text.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding all substrings of text that match any word in a large list. Checking every substring against the list directly is expensive.

2. Step 2: Recognize the trie + DFS pattern

   Building a trie from the words allows prefix-based pruning. DFS from each index in text efficiently finds all matching substrings without redundant checks, guaranteeing optimal time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie + DFS prunes search space better than brute force or binary search [OK]

Hint: Trie + DFS prunes prefix search efficiently [OK]

Common Mistakes:

• Thinking brute force is efficient enough for large inputs

2. Consider the following Python code implementing the bitwise trie approach to find maximum XOR of two numbers. Given the input nums = [2, 5], what is the value of current_xor after processing the number 5 in the second loop?

easy

A. 3

B. 6

C. 7

D. 5

Solution

1. Step 1: Trace bits of number 5

   5 in binary (32-bit) ends with bits ...00000101. We check bits from 31 down to 0.

2. Step 2: Traverse trie to maximize XOR

   For each bit, we try to go to the opposite bit in trie. For 5, the best XOR partner is 2 (binary 10). XOR of 5 and 2 is 7, so current_xor accumulates bits where toggled bit exists, resulting in 7.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Maximum XOR of 2 and 5 is 7, which matches current_xor after processing 5 [OK]

Hint: XOR bits accumulate where opposite bit exists [OK]

Common Mistakes:

• Confusing final max_xor with current_xor at iteration

3. You are given a 2D grid of letters and a list of words. You need to find all words from the list that can be formed by sequentially adjacent letters on the board, where adjacent letters are horizontally or vertically neighboring. Each letter cell may only be used once per word. Which algorithmic approach is best suited to efficiently solve this problem when the word list is large?

easy

A. Build a Trie from the word list and perform a single DFS on the board with prefix pruning using the Trie.

B. Use a brute force DFS for each word independently, checking all paths on the board.

C. Use dynamic programming to store subproblems of partial word matches on the board.

D. Sort the words and use binary search combined with DFS to find matches on the board.

Solution

1. Step 1: Understand problem constraints and prefix sharing

   Multiple words need to be found on the board, and many words may share prefixes, making prefix pruning beneficial.

2. Step 2: Use Trie for efficient prefix pruning during DFS

   Building a Trie allows pruning DFS paths early if no word starts with the current prefix, avoiding redundant searches and improving efficiency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie + DFS reduces search space drastically compared to checking each word separately [OK]

Hint: Trie + DFS prunes invalid prefixes early [OK]

Common Mistakes:

• Thinking brute force DFS per word is efficient
• Assuming DP applies here
• Using sorting and binary search without prefix pruning

4. Suppose the problem changes: you want to find the maximum XOR of two numbers in an array, but now numbers can be negative 32-bit integers. Which modification to the bitwise trie approach is necessary to handle negative numbers correctly?

hard

A. Use two's complement 32-bit representation and treat bits as unsigned during trie insertion and traversal

B. Ignore sign bit and only build trie from absolute values of numbers

C. Use 64-bit representation to store numbers in trie to avoid sign issues

D. Preprocess numbers by adding a large constant to make all numbers positive before building trie

Solution

1. Step 1: Understand representation of negative numbers

   Negative integers in 32-bit are stored in two's complement form, which can be treated as unsigned bit patterns for trie operations.

2. Step 2: Modify trie insertion and traversal

   Insert and traverse bits as unsigned 32-bit integers, including the sign bit, to correctly handle negative numbers.

3. Step 3: Avoid incorrect approaches

   Using 64-bit or adding constants changes problem semantics; ignoring sign bit loses information.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two's complement allows uniform bitwise trie handling of negative numbers [OK]

Hint: Two's complement bits can be treated as unsigned [OK]

Common Mistakes:

• Ignoring sign bit or converting to absolute values

5. Suppose the problem is modified so that root words can be reused multiple times to replace multiple prefixes in a single word (e.g., 'catcat' could be replaced by 'catcat' if 'cat' is a root). Which modification to the trie-based approach correctly handles this variant?

hard

A. Use the existing shortest prefix search once per word; no change needed as reuse is irrelevant.

B. After finding the shortest prefix, continue searching the remaining suffix recursively for more prefixes to replace.

C. Modify search to find the longest prefix instead of shortest, then recursively replace the suffix with roots.

D. Replace the entire word only if it exactly matches a root; otherwise, leave it unchanged.

Solution

1. Step 1: Understand reuse requirement

   Words can be replaced by concatenations of multiple root prefixes, so partial replacements must continue recursively.

2. Step 2: Modify search logic

   After finding a shortest prefix, recursively apply the same prefix search on the remaining suffix to replace all possible prefixes.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Recursive prefix replacement handles multiple root reuse correctly [OK]

Hint: Recursively replace suffixes after shortest prefix [OK]

Common Mistakes:

• Stopping after first prefix
• Searching for longest prefix only