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.