Trie Insert Operation in DSA Java - Execution Trace

Concept Flow - Trie Insert Operation

Start at root node

↓

For each character in word

↓

Check if child node exists

↓

Move to child

↓

After last char, mark node as end of word

↓

Done

Insert a word by moving from root through each character, creating nodes if missing, then mark the last node as word end.

Execution Sample

DSA Java

TrieNode root = new TrieNode();
insert(root, "cat");

void insert(TrieNode node, String word) {
  for (char c : word.toCharArray()) {
    if (node.children[c - 'a'] == null) node.children[c - 'a'] = new TrieNode();
    node = node.children[c - 'a'];
  }
  node.isEnd = true;
}

Inserts the word "cat" into the trie by creating nodes for 'c', 'a', and 't' if they don't exist, then marks the last node as end.

Execution Table

Step	Operation	Current Character	Node Created	Pointer Changes	Trie Visual State
1	Start at root	-	No	current = root	root (empty)
2	Check 'c' child	c	Yes	root.children['c'] = new TrieNode; current = root.children['c']	root → c
3	Check 'a' child	a	Yes	c.children['a'] = new TrieNode; current = c.children['a']	root → c → a
4	Check 't' child	t	Yes	a.children['t'] = new TrieNode; current = a.children['t']	root → c → a → t
5	Mark end of word	-	No	current.isEnd = true	root → c → a → t* (end)
6	Insert complete	-	No	-	Final trie with word "cat" inserted

💡 All characters processed; last node marked as end of word.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
current	root	node for 'c'	node for 'a'	node for 't'	node for 't'	node for 't'
node.children['c']	null	new TrieNode	new TrieNode	new TrieNode	new TrieNode	new TrieNode
node.children['a']	null	null	new TrieNode	new TrieNode	new TrieNode	new TrieNode
node.children['t']	null	null	null	new TrieNode	new TrieNode	new TrieNode
node.isEnd	false	false	false	false	true	true

Key Moments - 3 Insights

Why do we create a new node only if the child node for a character is null?

Because if the child node already exists, it means part of the word or another word shares that prefix, so we just move to that node (see steps 2-4 in execution_table). Creating a new node only when null avoids overwriting existing paths.

Why do we mark isEnd = true only after processing the last character?

Marking isEnd true signals that a complete word ends at this node. If we marked it earlier, it would incorrectly mark prefixes as complete words (see step 5 in execution_table).

What happens if we insert a word that shares prefix with an existing word?

We reuse existing nodes for shared characters and create new nodes only for the new suffix. This is why we check if child nodes exist before creating new ones (see concept_flow and steps 2-4).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the current node representing?

A Node for character 't'

B Node for character 'c'

C Node for character 'a'

D Root node

💡 Hint

Check the 'Pointer Changes' and 'Current Character' columns at step 3 in execution_table.

At which step does the trie mark the end of the inserted word?

A Step 2

B Step 5

C Step 4

D Step 6

💡 Hint

Look for the operation 'Mark end of word' in execution_table.

If the word 'cat' was already partially inserted and only 't' node was missing, how many new nodes would be created?

A 1

B 2

C 3

D 0

💡 Hint

Refer to concept_flow and variable_tracker to see when new nodes are created only if child is null.

Concept Snapshot

Trie Insert Operation:
- Start at root node
- For each character:
  - If child node exists, move to it
  - Else create new node and move
- After last char, mark node as end of word
- Shares prefixes to save space

Full Transcript

To insert a word into a trie, start at the root node. For each character in the word, check if a child node exists for that character. If it does, move to that child node. If not, create a new node for that character and move to it. After processing all characters, mark the last node as the end of a word. This process allows sharing prefixes among words, saving space. The execution table shows each step, including node creation and pointer changes. The variable tracker shows how the current pointer moves and when nodes are created. Key moments clarify why nodes are created only when missing and why marking the end happens last. The visual quiz tests understanding of pointer positions and node creation timing.

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