Trie Insert Operation in DSA Java

Mental Model

A trie stores words by branching letters step-by-step, sharing common prefixes to save space.

Analogy: Imagine a tree where each branch is a letter, and words grow by adding branches only when needed, like building a family tree of words.

root
 ↓
[ ]
Each node points to next letters, starting empty at root.

Dry Run Walkthrough

Input: Insert words: "cat", then "car" into an empty trie

Goal: Build a trie that stores both words sharing the prefix 'ca'

Step 1: Insert 'c' from 'cat' at root node

root -> c -> null
[inserted node for 'c']

Why: Start the first branch for the letter 'c'

Step 2: Insert 'a' after 'c'

root -> c -> a -> null
[branch for 'ca']

Why: Add next letter 'a' continuing the word

Step 3: Insert 't' after 'a' and mark end of word

root -> c -> a -> t* -> null
['*' marks end of 'cat']

Why: Complete the word 'cat' by marking end

Step 4: Insert 'r' after 'a' for word 'car'

root -> c -> a -> t* -> null
               ↓
               r* -> null
['r' branch added, marks end of 'car']

Why: Add new branch 'r' sharing prefix 'ca' and mark end

Result:

root -> c -> a -> t* -> null
               ↓
               r* -> null
Trie stores 'cat' and 'car' sharing prefix 'ca'

Annotated Code

DSA Java

import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

class Trie {
    private final TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current.children.putIfAbsent(ch, new TrieNode()); // add node if missing
            current = current.children.get(ch); // move to next node
        }
        current.isEndOfWord = true; // mark end of word
    }

    public void printTrie() {
        printTrieHelper(root, "");
    }

    private void printTrieHelper(TrieNode node, String prefix) {
        if (node.isEndOfWord) {
            System.out.println(prefix + "*"); // mark end of word
        }
        for (char ch : node.children.keySet()) {
            printTrieHelper(node.children.get(ch), prefix + ch);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        trie.insert("car");
        trie.printTrie();
    }
}

current.children.putIfAbsent(ch, new TrieNode());

Add new node for letter if it does not exist

current = current.children.get(ch);

Move current pointer to child node for next letter

current.isEndOfWord = true;

Mark current node as end of a complete word

Output

cat*

car*

Complexity Analysis

Time: O(m) because we process each letter of the word once during insertion

Space: O(m) in worst case when all letters are new and need new nodes

vs Alternative: Compared to storing words in a list, trie insertion is faster for prefix queries and avoids duplicate prefix storage

Edge Cases

Insert empty string

No nodes added, root remains unchanged

DSA Java

for (char ch : word.toCharArray()) {

Insert word that is prefix of existing word (e.g., insert 'ca' after 'cat')

Existing nodes reused, end of word marked at prefix node

DSA Java

current.isEndOfWord = true;

Insert duplicate word

No new nodes added, end of word remains marked

DSA Java

current.children.putIfAbsent(ch, new TrieNode());

When to Use This Pattern

When you need to store many words sharing prefixes and quickly check or insert them, use a trie insert pattern to build a prefix tree efficiently.

Common Mistakes

Mistake: Not marking the end of word node, so words are not recognized as complete
Fix: Always set isEndOfWord = true after inserting all letters of a word

Mistake: Creating new nodes even if the letter node already exists, causing duplicates
Fix: Check if child node exists before creating new node using putIfAbsent or equivalent

Summary

Inserts words letter by letter into a tree structure sharing prefixes.

Use when storing many words to save space and enable fast prefix queries.

The key is to reuse existing nodes for shared prefixes and mark ends of words.

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