Trie insertion and search in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

How does a Trie store words?

Which statement best describes how a Trie stores multiple words?

A Words are stored as separate arrays linked to the root node.

B Each node stores a whole word, and children represent synonyms.

C Each node stores the frequency of the word it represents.

D Each node represents a character, and paths from root to leaves form words.

💡 Hint

Think about how characters connect to form words in a tree structure.

A Trie stores words by linking characters in nodes. Each path from the root to a node spells out a prefix or a full word.

📋 Factual

intermediate

What marks the end of a word in a Trie?

In a Trie, how is the end of a word typically indicated?

A By a special boolean flag in the node.

B By storing the full word in the last node.

C By having no children nodes.

D By linking to a separate list of words.

💡 Hint

Consider how the Trie distinguishes prefixes from complete words.

Each node has a boolean flag that marks if the path to that node forms a complete word.

🚀 Application

advanced

Result of inserting words into a Trie

After inserting the words "cat", "car", and "dog" into an empty Trie, how many children does the root node have?

A 2

B 3

C 1

D 4

💡 Hint

Look at the first letters of each word.

Words "cat" and "car" start with 'c', so one child node for 'c'. "dog" starts with 'd', so another child node for 'd'. Total 2 children.

🔍 Analysis

advanced

Searching a word in a Trie

What happens when you search for the word "bat" in a Trie that contains only "cat" and "car"?

A "bat" is found because 'a' and 't' exist in the Trie.

B "bat" is not found because the path for 'b' does not exist.

C "bat" is found because it shares prefix 'a' with "cat".

D Search returns true because 't' is a child of 'c'.

💡 Hint

Check if the first character of the search word exists in the Trie.

The Trie has no child node for 'b' at the root, so "bat" cannot be found.

❓ Reasoning

expert

Number of nodes after multiple insertions

Starting with an empty Trie, you insert the words: "to", "tea", "ted", "ten", and "inn". How many nodes does the Trie contain after all insertions?

A 11

B 12

C 10

D 13

💡 Hint

Count shared prefixes carefully to avoid double counting nodes.

Words share prefixes: "to" and "tea", "ted", "ten" share 't' and 'e'. Counting unique nodes results in 10 nodes total.

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