Trie Insert Operation in DSA Java - Time & Space Complexity

Time Complexity: Trie Insert Operation

O(n)

Understanding Time Complexity

We want to understand how long it takes to add a word into a trie data structure.

The question is: how does the time grow as the word gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void insert(String word) {
    TrieNode current = root;
    for (int i = 0; i < word.length(); i++) {
        char ch = word.charAt(i);
        current.children.putIfAbsent(ch, new TrieNode());
        current = current.children.get(ch);
    }
    current.isEndOfWord = true;
}

This code adds each character of the word into the trie, creating nodes if needed.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character of the word.
• How many times: Exactly once per character, so as many times as the word's length.

How Execution Grows With Input

As the word gets longer, the number of steps grows directly with its length.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The time grows in a straight line with the word length.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert grows directly with the length of the word.

Common Mistake

[X] Wrong: "Inserting a word takes constant time because we just add one word."

[OK] Correct: Each character must be processed, so longer words take more time.

Interview Connect

Knowing how trie insertion scales helps you explain efficient word storage and search in interviews.

Self-Check

"What if we changed the data structure to use an array of fixed size for children instead of a map? How would the time complexity change?"

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