Implement Trie (Prefix Tree)

▶

Steps

setup

Initialize Trie with Root Node

Create the root node of the trie, which is empty and has no children or end-of-word flag set.

💡 The root node is the starting point for all insertions and searches; it represents an empty prefix.

Line:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False

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

💡 The trie starts empty with a single root node ready to build from.

insert

Insert 'apple' - Insert 'a' Node

Start inserting 'apple' by checking if 'a' exists as a child of root. It does not, so create a new node for 'a'.

💡 Each new character not found in children requires creating a new node to extend the trie.

Line:

for ch in word:
    if ch not in node.children:
        node.children[ch] = TrieNode()
    node = node.children[ch]

💡 New nodes are created only when the character path does not exist, ensuring shared prefixes are reused.

insert

Insert 'apple' - Insert 'p' Node (First 'p')

Check if 'p' exists as a child of 'a'. It does not, so create a new node for 'p'. Move to this node.

💡 Insertion continues character by character, creating nodes as needed.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()
node = node.children[ch]

💡 The trie branches out only when new characters appear at a given prefix.

insert

Insert 'apple' - Insert 'p' Node (Second 'p')

Check if second 'p' exists as a child of first 'p'. It does not, so create a new node for second 'p'. Move to this node.

💡 Repeated characters are treated as separate nodes along the path.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()
node = node.children[ch]

💡 Each character in the word corresponds to a node, even if repeated.

insert

Insert 'apple' - Insert 'l' Node

Check if 'l' exists as a child of second 'p'. It does not, so create a new node for 'l'. Move to this node.

💡 Insertion continues until all characters are added.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()
node = node.children[ch]

💡 Nodes are created only when the path does not exist, preserving shared prefixes.

insert

Insert 'apple' - Insert 'e' Node and Mark End

Check if 'e' exists as a child of 'l'. It does not, so create a new node for 'e'. Mark this node as end of word.

💡 The last character node is marked to indicate a complete word ends here.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()
node = node.children[ch]
node.isEnd = True

💡 Marking isEnd distinguishes words that share prefixes but differ in length.

search

Search 'apple' - Traverse 'a'

Start searching for 'apple' from root. Check if 'a' exists as a child of root. It does, move to node 'a'.

💡 Search traverses existing nodes matching each character.

Line:

for ch in word:
    if ch not in node.children:
        return False
    node = node.children[ch]

💡 Search succeeds only if all characters are found sequentially.

search

Search 'apple' - Traverse 'p', 'p', 'l', 'e'

Continue traversing nodes for 'p', second 'p', 'l', and 'e' sequentially. All nodes exist.

💡 Each character must be found in children to continue search.

Line:

for ch in word:
    if ch not in node.children:
        return False
    node = node.children[ch]
return node.isEnd

💡 The search returns true only if the last node marks end of a word.

search

Search 'app' - Traverse 'a', 'p', 'p'

Search for 'app' by traversing nodes 'a', 'p', and second 'p'. All nodes exist.

💡 Search follows the path for the prefix but must check end-of-word flag.

Line:

for ch in word:
    if ch not in node.children:
        return False
    node = node.children[ch]
return node.isEnd

💡 A prefix existing in trie does not guarantee the word exists unless isEnd is true.

search

startsWith 'app' - Traverse 'a', 'p', 'p'

Check if prefix 'app' exists by traversing nodes 'a', 'p', and second 'p'. All nodes exist.

💡 startsWith returns true if prefix path exists regardless of isEnd flag.

Line:

for ch in prefix:
    if ch not in node.children:
        return False
    node = node.children[ch]
return True

💡 startsWith confirms presence of prefix even if word is not complete.

insert

Insert 'app' - Traverse 'a', 'p', 'p' Nodes

Insert 'app' by traversing existing nodes for 'a', 'p', and second 'p' since they already exist.

💡 Existing nodes are reused during insertion to avoid duplication.

Line:

for ch in word:
    if ch not in node.children:
        node.children[ch] = TrieNode()
    node = node.children[ch]

💡 Trie efficiently shares prefixes among words.

insert

Insert 'app' - Mark 'p' Node as End of Word

Mark the node for second 'p' as end of word to indicate 'app' is now a complete word in the trie.

💡 Marking isEnd true differentiates 'app' as a word distinct from 'apple'.

Line:

node.isEnd = True

💡 Words sharing prefixes can end at different nodes.

search

Search 'app' - Traverse 'a', 'p', 'p' and Check End

Search for 'app' by traversing nodes 'a', 'p', and second 'p'. Node for second 'p' is marked as end of word.

💡 Search returns true only if the last node is marked as end of word.

Line:

for ch in word:
    if ch not in node.children:
        return False
    node = node.children[ch]
return node.isEnd

💡 Marking isEnd true enables recognition of shorter words sharing prefixes with longer words.

class TrieNode:
    def __init__(self):
        self.children = {}  # STEP 1
        self.isEnd = False  # STEP 1

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

    def insert(self, word: str) -> None:
        node = self.root  # STEP 2
        for ch in word:  # STEP 2-6
            if ch not in node.children:  # STEP 2-6
                node.children[ch] = TrieNode()  # STEP 2-6
            node = node.children[ch]  # STEP 2-6
        node.isEnd = True  # STEP 6, 12

    def search(self, word: str) -> bool:
        node = self.root  # STEP 7
        for ch in word:  # STEP 7-9, 13
            if ch not in node.children:  # STEP 7-9, 13
                return False  # STEP 9
            node = node.children[ch]  # STEP 7-9, 13
        return node.isEnd  # STEP 8, 9, 13

    def startsWith(self, prefix: str) -> bool:
        node = self.root  # STEP 10
        for ch in prefix:  # STEP 10
            if ch not in node.children:  # STEP 10
                return False  # STEP 10
            node = node.children[ch]  # STEP 10
        return True  # STEP 10

# Driver code
trie = Trie()  # STEP 1
trie.insert('apple')  # STEP 2-6
print(trie.search('apple'))  # STEP 7-8
print(trie.search('app'))    # STEP 9
print(trie.startsWith('app')) # STEP 10
trie.insert('app')  # STEP 11-12
print(trie.search('app'))    # STEP 13

📊

Implement Trie (Prefix Tree) - Watch the Algorithm Execute, Step by Step

Watching each character insertion and traversal helps you understand how tries efficiently store and query strings by sharing prefixes.

insert

insert

apple

a

insert

apple

ap

insert

apple

app

insert

apple

appl

insert

apple

apple*

search

apple

apple*

search

apple

apple*

Search: true

search

app

apple*

Search: false

startsWith

app

apple*

Search: true

insert

app

apple*

insert

app

app*le*

search

app

app*le*

Search: true

Key Takeaways

✓ Tries efficiently store words by sharing common prefixes, reducing redundant storage.

This is hard to see from code alone because the structure is implicit; visualization shows node sharing clearly.

✓ The isEnd flag on nodes distinguishes between prefixes and complete words.

Without visualization, it's easy to confuse prefix presence with full word presence.

✓ Insertion reuses existing nodes for shared prefixes, creating new nodes only when necessary.

Visualizing each node creation and traversal clarifies how tries grow dynamically.

Practice

1. You are given a list of words and need to find all words that can be formed by concatenating two or more shorter words from the same list. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Trie construction combined with DFS and memoization to efficiently check concatenations

B. Greedy approach that tries to match the longest prefix repeatedly

C. Dynamic programming on substring indices without any prefix tree structure

D. Sorting words by length and checking concatenations using a hash set only

Solution

1. Step 1: Understand the problem requires checking multiple concatenations efficiently

   Naive substring checks or greedy prefix matches fail to handle overlapping prefixes and repeated subproblems efficiently.

2. Step 2: Recognize Trie + DFS with memoization optimizes prefix lookups and avoids recomputation

   Trie allows fast prefix matching; DFS explores concatenations; memoization caches results to prevent exponential recomputation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie + DFS + memoization is the known optimal approach [OK]

Hint: Trie + DFS + memoization handles prefix and repeated subproblems efficiently [OK]

Common Mistakes:

• Assuming greedy prefix matching always works
• Using DP without prefix optimization

2. 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

3. Given a string s and a dictionary of words, you want to determine if s can be segmented into a sequence of dictionary words. Which approach guarantees an optimal solution that efficiently checks prefixes and avoids repeated substring checks?

easy

A. Greedy approach that picks the longest matching prefix at each step

B. Iterative dynamic programming combined with a trie to check prefixes efficiently

C. Pure brute force recursion checking all substring partitions without memoization

D. Sorting the dictionary and using binary search to check substrings

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking if the string can be segmented into dictionary words, which involves many substring checks.

2. Step 2: Evaluate approaches for efficiency

   Greedy fails because longest prefix may not lead to a solution; brute force is exponential; binary search is inefficient for substring checks. Using a trie with DP allows prefix checks in O(m) time per position, avoiding repeated substring checks.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie + DP efficiently prunes invalid prefixes [OK]

Hint: Trie + DP avoids repeated substring checks [OK]

Common Mistakes:

• Assuming greedy longest prefix always works
• Using brute force without memoization
• Using binary search for substring checks

4. 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

5. Consider the following buggy code snippet for the longest word in dictionary problem. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line: queue.append(child) without checking if child.word is not None

B. Line: for ch in sorted(node.children.keys())

C. Line: node.word = word in insert method

D. Line: trie.insert(word) in the for loop

Solution

1. Step 1: Identify enqueue condition

   The BFS queue should only include nodes representing complete words (child.word != None) to ensure all prefixes are valid.

2. Step 2: Locate the bug

   The code enqueues all children regardless of whether they represent complete words, allowing invalid prefixes to be considered, breaking the prefix condition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Enqueueing invalid prefix nodes causes incorrect longest word [OK]

Hint: Only enqueue nodes with complete words in BFS [OK]

Common Mistakes:

• Enqueueing all children regardless of word completion
• Misplacing word assignment in insert
• Sorting children incorrectly