Trie Insert Operation in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. Each node represents a character, and paths down the tree represent words.

beginner

What is the main purpose of the insert operation in a Trie?

The insert operation adds a new word into the Trie by creating nodes for characters that don't exist and marking the end of the word.

beginner

In the Trie insert operation, what does marking the end of a word mean?

It means setting a special flag (often called 'isEndOfWord') in the last node of the inserted word to true, indicating that a complete word ends there.

intermediate

What happens if a character of the word to insert already exists in the Trie?

If the character node exists, the insert operation moves to that node without creating a new one and continues with the next character.

intermediate

Why is a Trie efficient for prefix-based searches?

Because common prefixes share the same path in the Trie, making it fast to find all words starting with a given prefix by traversing the shared nodes.

What does the insert operation do when it encounters a character node that already exists in the Trie?

A Skips to the next character node

B Creates a new node for that character

C Deletes the existing node

D Marks the node as end of word immediately

If the character node exists, the insert operation moves to that node and continues inserting the next character.

How does the Trie indicate the end of a word after insertion?

A By setting a flag in the last character's node

B By reversing the word in the Trie

C By deleting the last node

D By adding a special child node

The end of a word is marked by setting a boolean flag (like 'isEndOfWord') in the last node of the inserted word.

Which of these is NOT true about the Trie insert operation?

A It creates new nodes for characters not present

B It removes existing nodes if the word is a prefix

C It marks the end of the word after insertion

D It moves through existing nodes for shared prefixes

The insert operation does not remove existing nodes; it only adds new nodes or marks the end of the word.

What is the time complexity of inserting a word of length n into a Trie?

A O(n^2)

B O(1)

C O(n)

D O(log n)

Insertion takes O(n) time where n is the length of the word, as each character is processed once.

Why is Trie insert operation useful for autocomplete features?

A Because it stores words in sorted order

B Because it deletes unused words automatically

C Because it compresses words into single nodes

D Because it allows quick prefix matching

Trie allows fast prefix matching, which is essential for autocomplete to find all words starting with a given prefix.

Explain step-by-step how the insert operation works in a Trie when adding a new word.

Think about walking through the Trie character by character.

Describe why marking the end of a word is important in a Trie insert operation.

Consider what happens if you search for a word that is a prefix of another.

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