Trie Insert Operation in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting words into a Trie

What is the output of the following Java code that inserts words into a Trie and prints the Trie structure?

DSA Java

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord = false;
}

class Trie {
    TrieNode root = new TrieNode();

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

    void printTrie(TrieNode node, String prefix) {
        if (node.isEndOfWord) {
            System.out.println(prefix);
        }
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                printTrie(node.children[i], prefix + (char)(i + 'a'));
            }
        }
    }

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

A

car
cat
dog

B

cat
car
dog

C

dog
car
cat

D

car
dog
cat

💡 Hint

Think about how the printTrie method traverses children in alphabetical order.

The printTrie method recursively prints words in alphabetical order because it iterates children from index 0 to 25. 'car' comes before 'cat' alphabetically, so it prints 'car' first, then 'cat', then 'dog'.

❓ Predict Output

intermediate

Output after inserting overlapping prefixes in Trie

What is the output of this Java code after inserting words with overlapping prefixes into a Trie and printing all stored words?

DSA Java

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord = false;
}

class Trie {
    TrieNode root = new TrieNode();

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

    void printTrie(TrieNode node, String prefix) {
        if (node.isEndOfWord) {
            System.out.println(prefix);
        }
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                printTrie(node.children[i], prefix + (char)(i + 'a'));
            }
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("app");
        trie.insert("apple");
        trie.insert("application");
        trie.printTrie(trie.root, "");
    }
}

A

app
application
apple

B

apple
app
application

C

application
apple
app

D

app
apple
application

💡 Hint

Words are printed in alphabetical order due to child traversal from 'a' to 'z'.

The Trie stores 'app', 'apple', and 'application'. The printTrie method prints words in alphabetical order. 'app' comes before 'apple' and 'application', so it prints in that order.

🔧 Debug

advanced

Identify the error in Trie insert method

What error will this Java code produce when inserting a word into the Trie?

DSA Java

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord = false;
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }
}

A ArrayIndexOutOfBoundsException

B NullPointerException

C StringIndexOutOfBoundsException

D No error, runs correctly

💡 Hint

Check the loop boundary condition for accessing characters in the string.

The loop uses i <= word.length(), which tries to access word.charAt(word.length()), causing StringIndexOutOfBoundsException because valid indices are 0 to length-1.

❓ Predict Output

advanced

Output after inserting words with shared prefixes and printing

What is the output of this Java code after inserting words with shared prefixes and printing all words stored in the Trie?

DSA Java

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord = false;
}

class Trie {
    TrieNode root = new TrieNode();

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

    void printTrie(TrieNode node, String prefix) {
        if (node.isEndOfWord) {
            System.out.println(prefix);
        }
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                printTrie(node.children[i], prefix + (char)(i + 'a'));
            }
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("bat");
        trie.insert("bath");
        trie.insert("batman");
        trie.insert("batmobile");
        trie.printTrie(trie.root, "");
    }
}

A

bat
bath
batman
batmobile

B

batmobile
batman
bath
bat

C

bat
batman
bath
batmobile

D

bath
bat
batman
batmobile

💡 Hint

Words are printed in alphabetical order due to child traversal from 'a' to 'z'.

The printTrie method prints words in alphabetical order. 'bat' comes before 'bath', which comes before 'batman' and 'batmobile'.

🧠 Conceptual

expert

Number of nodes after inserting words into Trie

If you insert the words ["go", "gone", "guild", "guilt"] into an empty Trie, how many Trie nodes will be created in total (including the root node)?

A 12

B 10

C 11

D 13

💡 Hint

Count unique characters in the paths, including shared prefixes, plus the root node.

Root node counts as 1. The words share prefix 'g'. The unique nodes created are: root(1), 'g'(2), 'o'(3), 'n'(4), 'e'(5), 'u'(6), 'i'(7), 'l'(8), 'd'(9), 't'(10). Total nodes = 10.

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