Trie insertion and search in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a character into the Trie node's children.

Data Structures Theory

node.children[[1]] = TrieNode()

Drag options to blanks, or click blank then click option'

Aword

Bchar

Cindex

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole word or index instead of the character as the key.

The character char is used as the key to insert a new TrieNode into the children dictionary.

2fill in blank

medium

Complete the code to check if a character exists in the current Trie node's children during search.

Data Structures Theory

if [1] in node.children:

Drag options to blanks, or click blank then click option'

Aword

Bnode

Cchar

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for the whole word or index instead of the character.

We check if the current character char exists in the children of the current node.

3fill in blank

hard

Fix the error in the code that marks the end of a word in the Trie after insertion.

Data Structures Theory

node.[1] = True

Drag options to blanks, or click blank then click option'

Ais_end_of_word

Bend

Cis_word

Dword_end

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect attribute names like 'end' or 'word_end' which are not standard.

The standard attribute to mark the end of a word in a Trie node is is_end_of_word.

4fill in blank

hard

Fill both blanks to complete the dictionary comprehension that creates a mapping of characters to Trie nodes for a given word.

Data Structures Theory

{ [1]: TrieNode() for [2] in word }

Drag options to blanks, or click blank then click option'

Achar

Bnode

Cletter

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node' or 'word' as keys or loop variables which are incorrect.

The comprehension maps each char in the word to a new TrieNode.

5fill in blank

hard

Fill all three blanks to complete the search function that returns True if the word exists in the Trie.

Data Structures Theory

def search(word):
    node = root
    for [1] in word:
        if [2] not in node.children:
            return False
        node = node.children[[3]]
    return node.is_end_of_word

Drag options to blanks, or click blank then click option'

Achar

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names or the whole word instead of characters.

Each blank should be filled with char because the loop iterates over characters, and the search checks and moves along those characters in the Trie.

Practice

1. What is the main purpose of a Trie data structure in storing words?

easy

A. To store words letter by letter in a tree for fast prefix search

B. To store words as a single string in a list

C. To store words in random order for quick access

D. To store words using hash codes only

Solution

1. Step 1: Understand Trie structure

   A Trie stores words by breaking them into letters and linking them in a tree structure.

2. Step 2: Identify purpose

   This structure allows fast searching of words by prefixes, unlike storing whole words as strings or hashes.

3. Final Answer:

   To store words letter by letter in a tree for fast prefix search -> Option A

4. Quick Check:

   Trie = letter-by-letter tree [OK]

Hint: Trie stores words letter by letter for prefix search [OK]

Common Mistakes:

• Thinking Trie stores whole words as strings
• Confusing Trie with hash tables
• Assuming Trie stores words randomly

2. Which of the following correctly describes the insertion process in a Trie?

easy

A. Replace existing nodes with new letters

B. Add the whole word as a single node

C. Insert letters only if the word is not already present

D. Add nodes for each letter if missing and mark the last node as end of word

Solution

1. Step 1: Review insertion steps

   Insertion checks each letter; if a letter node is missing, it creates it.

2. Step 2: Mark end of word

   After all letters are inserted, the last node is marked to show the word ends there.

3. Final Answer:

   Add nodes for each letter if missing and mark the last node as end of word -> Option D

4. Quick Check:

   Insert = add letters + mark end [OK]

Hint: Insert letter nodes if missing, mark last as word end [OK]

Common Mistakes:

• Inserting whole word as one node
• Not marking the end of word
• Replacing existing nodes unnecessarily

3. Given a Trie with words: cat, car, and dog, what will be the result of searching for cap?

medium

A. True, because 'cap' is similar to 'car'

B. True, because 'ca' prefix exists

C. False, because 'p' node does not exist after 'ca'

D. Error, search cannot handle missing nodes

Solution

1. Step 1: Check prefix nodes

   The Trie has nodes for 'c' and 'a' from 'cat' and 'car'.

2. Step 2: Verify next letter node

   There is no 'p' node after 'a', so 'cap' is not found.

3. Final Answer:

   False, because 'p' node does not exist after 'ca' -> Option C

4. Quick Check:

   Missing letter node means word not found [OK]

Hint: Search fails if any letter node missing [OK]

Common Mistakes:

• Assuming prefix presence means full word found
• Confusing similar words as found
• Expecting errors instead of false

4. Identify the error in this Trie insertion pseudocode:

for letter in word:
  if letter in current_node:
    current_node = current_node[letter]
  else:
    current_node[letter] = {}
current_node['end'] = True

medium

A. The 'end' marker is set outside the loop, should be inside

B. The else block should update current_node after adding new node

C. The loop should iterate over indices, not letters

D. The code incorrectly uses a dictionary for nodes

Solution

1. Step 1: Analyze insertion logic

   When a new letter node is created, the code does not move current_node to this new node.

2. Step 2: Identify fix

   After adding a new node, current_node must be updated to that node to continue insertion correctly.

3. Final Answer:

   The else block should update current_node after adding new node -> Option B

4. Quick Check:

   Update current_node after adding new letter node [OK]

Hint: Move current_node after adding new node [OK]

Common Mistakes:

• Not updating current_node after insertion
• Setting 'end' marker inside loop incorrectly
• Confusing iteration over letters vs indices

5. You want to insert the words bat, bath, and baton into a Trie. How many nodes will the Trie have after all insertions?

hard

A. 9 nodes

B. 8 nodes

C. 7 nodes

D. 10 nodes

Solution

1. Step 1: Insert 'bat'

   Creates nodes: 'b', 'a', 't' -> 3 nodes (root is not counted as a node).

2. Step 2: Insert 'bath'

   'b', 'a', 't' exist; add 'h' -> 1 new node; total 4 nodes.

3. Step 3: Insert 'baton'

   'b', 'a', 't' exist; add 'o', 'n' -> 2 new nodes; total 6 nodes.

4. Step 4: Count 'end' markers as nodes

   Each word end is marked, adding 3 'end' markers as nodes; total nodes = 6 + 3 = 9 nodes.

5. Step 5: Confirm total nodes

   Nodes: b, a, t, h, o, n plus 3 'end' markers = 9 nodes.

6. Final Answer:

   9 nodes -> Option A

7. Quick Check:

   Letter nodes + end markers = 9 [OK]

Hint: Count letter nodes plus 'end' markers as nodes = 9 [OK]

Common Mistakes:

• Counting duplicate nodes multiple times
• Ignoring shared prefixes
• Miscounting letters in longer words
• Not counting 'end' markers as nodes