Trie Insert Operation in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new TrieNode in the insert method.

DSA Java

if (node.children[c - 'a'] == null) {
    node.children[c - 'a'] = new [1]();
}

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

ATrieNode

BString

CArrayList

DHashMap

Attempts:

3 left

💡 Hint

Common Mistakes

Using String or other types instead of TrieNode.

Forgetting to create a new node before assigning.

We create a new TrieNode object to represent the child node for the character.

2fill in blank

medium

Complete the code to mark the end of a word in the insert method.

DSA Java

node.[1] = true;

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

AisEnd

BisWord

CendOfWord

DwordEnd

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect field names like isWord or wordEnd.

Not marking the end of the word at all.

The boolean field isEnd marks that this node represents the end of a word.

3fill in blank

hard

Fix the error in the loop that iterates over characters in the insert method.

DSA Java

for (int i = 0; i [1] word.length(); i++) {
    char c = word.charAt(i);
    // rest of code
}

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

A<=

B>

C<

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' causes index out of bounds error.

Using '>' or '>=' causes the loop to never run.

The loop should run while i is less than word.length() to avoid index out of bounds.

4fill in blank

hard

Fill both blanks to correctly update the node pointer and access children array.

DSA Java

node = node.children[[1] - [2]];

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

Ac

B'a'

C'z'

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'z' instead of 'a' for subtraction.

Using loop index i instead of character c.

We subtract 'a' from character c to get the correct index in children array.

5fill in blank

hard

Fill all three blanks to complete the insert method's loop and marking end of word.

DSA Java

for (int [1] = 0; i [2] word.length(); [3]++) {
    char c = word.charAt(i);
    if (node.children[c - 'a'] == null) {
        node.children[c - 'a'] = new TrieNode();
    }
    node = node.children[c - 'a'];
}
node.isEnd = true;

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

Ai

B<

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong loop variable names.

Using wrong loop condition operators.

Forgetting to increment the loop variable.

The loop uses variable i starting at 0, runs while i < word.length(), and increments i each time.

Practice

1. What is the main purpose of the insert operation in a Trie data structure?

easy

A. To count the number of words stored in the Trie

B. To delete a word from the Trie

C. To add a new word character by character into the Trie

D. To search for a word in the Trie

Solution

1. Step 1: Understand the insert operation

   The insert operation adds each character of a word into the Trie, creating nodes if needed.

2. Step 2: Identify the purpose of insert

   It builds the Trie structure by adding new words character by character.

3. Final Answer:

   To add a new word character by character into the Trie -> Option C

4. Quick Check:

   Insert = Add word stepwise [OK]

Hint: Insert means adding word letters step-by-step [OK]

Common Mistakes:

• Confusing insert with search or delete
• Thinking insert counts words
• Assuming insert removes words

2. Which of the following is the correct way to start inserting a word "cat" into a Trie in Java?

easy

A. for (int i = 0; i < word.length(); i++)

B. for (int i = 0; i <= word.length(); i++)

C. for (int i = 1; i < word.length(); i++)

D. for (int i = 1; i <= word.length(); i++)

Solution

1. Step 1: Check loop boundaries for string indexing

   Java strings are zero-indexed, so loop should start at 0 and go to length-1.

2. Step 2: Choose correct loop condition

   The loop must run while i < word.length() to cover all characters.

3. Final Answer:

   for (int i = 0; i < word.length(); i++) -> Option A

4. Quick Check:

   Loop from 0 to length-1 [OK]

Hint: Use i < length for zero-based string loops [OK]

Common Mistakes:

• Using <= causes index out of bounds
• Starting loop at 1 skips first character
• Using wrong loop limits

3. What will be the state of the Trie after inserting the words "bat" and "ball" in order? Assume each node stores a character and a boolean isEnd to mark word end.

medium

A. "b" -> "a" -> "l" -> "l" (isEnd=true), "a" -> "t" (isEnd=true)

B. "b" -> "a" -> "t" (isEnd=true), "t" -> "l" -> "l" (isEnd=true)

C. "b" -> "a" -> "l" -> "l" (isEnd=false), "t" (isEnd=true)

D. "b" -> "a" -> "t" (isEnd=true), "a" -> "l" -> "l" (isEnd=true)

Solution

1. Step 1: Insert "bat" into Trie

   Insert nodes for 'b' -> 'a' -> 't' and mark 't' node as word end.

2. Step 2: Insert "ball" sharing prefix

   Reuse 'b' -> 'a', then add 'l' -> 'l' nodes and mark last 'l' as word end.

3. Final Answer:

   "b" -> "a" -> "t" (isEnd=true), "a" -> "l" -> "l" (isEnd=true) -> Option D

4. Quick Check:

   Shared prefix 'ba', separate endings [OK]

Hint: Shared prefix nodes reused, endings marked separately [OK]

Common Mistakes:

• Not marking correct end nodes
• Creating separate branches for shared prefix
• Confusing node characters and word ends

4. Given the following Java code snippet for inserting a word into a Trie, what is the error?

void insert(String word) {
  TrieNode node = root;
  for (int i = 0; i <= word.length(); i++) {
    char ch = word.charAt(i);
    if (!node.children.containsKey(ch)) {
      node.children.put(ch, new TrieNode());
    }
    node = node.children.get(ch);
  }
  node.isEnd = true;
}

medium

A. Missing initialization of root node

B. Loop condition should be i < word.length(), not i <= word.length()

C. Should use node.children.get(ch) before checking containsKey

D. isEnd should be set before the loop

Solution

1. Step 1: Analyze loop boundary

   The loop uses i <= word.length(), which causes index out of bounds on charAt.

2. Step 2: Correct loop condition

   It should be i < word.length() to avoid accessing invalid index.

3. Final Answer:

   Loop condition should be i < word.length(), not i <= word.length() -> Option B

4. Quick Check:

   Index error fixed by i < length [OK]

Hint: Loop to length-1 for string indexing [OK]

Common Mistakes:

• Using <= causes runtime error
• Setting isEnd inside loop
• Checking children incorrectly

5. You want to insert the words "apple", "app", and "ape" into a Trie. After insertion, which of the following statements is TRUE about the Trie structure?

hard

A. The node for the second 'p' after 'a' will have isEnd = true because of "app"

B. The node for 'e' after 'a' will have isEnd = false because "ape" is not a full word

C. The node for 'l' after 'p' will have isEnd = false because "apple" is not inserted fully

D. All nodes except root have isEnd = true

Solution

1. Step 1: Insert "apple" and "app" sharing prefix

   Both share 'a' -> 'p' -> 'p'. The second 'p' node marks end for "app".

2. Step 2: Insert "ape" branching at second character

   From 'a', branch to 'p' then 'e' node marked as end for "ape".

3. Step 3: Check isEnd flags

   The second 'p' node after 'a' has isEnd true for "app"; 'e' node after 'p' has isEnd true for "ape"; final 'e' node for "apple" has isEnd true.

4. Final Answer:

   The node for the second 'p' after 'a' will have isEnd = true because of "app" -> Option A

5. Quick Check:

   Shared prefix nodes mark word ends correctly [OK]

Hint: Shared prefixes mark ends for shorter words [OK]

Common Mistakes:

• Assuming branch nodes can't be word ends
• Thinking partial words are not marked
• Marking all nodes as word ends