Trie Node Design and Initialization in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the children array for a Trie node.

DSA Java

private TrieNode[] children = new TrieNode[[1]];

Drag options to blanks, or click blank then click option'

A10

B52

C26

D128

Attempts:

3 left

💡 Hint

Common Mistakes

Using 52 for uppercase and lowercase combined when only lowercase is needed.

Using 10 which is for digits, not letters.

A Trie node for lowercase English letters needs an array of size 26 for each letter.

2fill in blank

medium

Complete the constructor to initialize the isEndOfWord flag to false.

DSA Java

public TrieNode() {
    this.isEndOfWord = [1];
}

Drag options to blanks, or click blank then click option'

Afalse

Btrue

Cnull

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting isEndOfWord to true by default.

Using null or 0 which are invalid for boolean.

When a Trie node is created, it should not mark the end of a word initially, so false is correct.

3fill in blank

hard

Fix the error in the method to check if a child node exists for a given character.

DSA Java

public boolean containsKey(char ch) {
    return children[[1]] != null;
}

Drag options to blanks, or click blank then click option'

Ach - 'A'

Bch + 'a'

Cch

Dch - 'a'

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'A' instead of 'a' which is uppercase and causes wrong indexing.

Using the character directly which is not an integer index.

To map 'a' to 0, subtract 'a' from the character to get the correct index.

4fill in blank

hard

Fill both blanks to insert a child node for a character and mark the end of a word.

DSA Java

public void put(char ch, TrieNode node) {
    children[[1]] = node;
}

public void setEnd() {
    isEndOfWord = [2];
}

Drag options to blanks, or click blank then click option'

Ach - 'a'

Btrue

Cfalse

Dch

Attempts:

3 left

💡 Hint

Common Mistakes

Using character directly as index.

Setting isEndOfWord to false when marking end.

Use 'ch - 'a'' to find the index and set isEndOfWord to true when marking the end.

5fill in blank

hard

Fill all three blanks to get a child node, check if node is end, and initialize children array.

DSA Java

public TrieNode get(char ch) {
    return children[[1]];
}

public boolean isEnd() {
    return [2];
}

public TrieNode() {
    children = new TrieNode[[3]];
    isEndOfWord = false;
}

Drag options to blanks, or click blank then click option'

Ach - 'a'

BisEndOfWord

C26

Dch

Attempts:

3 left

💡 Hint

Common Mistakes

Using character directly as index.

Returning wrong variable in isEnd method.

Initializing children array with wrong size.

Use 'ch - 'a'' for index, return isEndOfWord flag, and initialize children array with size 26.

Practice

1. What is the primary purpose of a Trie node in a Trie data structure?

easy

A. To act as a pointer to the next node in a linked list

B. To store characters and links to child nodes representing prefixes

C. To hold the entire word as a string

D. To store integer values only

Solution

1. Step 1: Understand the role of Trie nodes

   A Trie node stores a character and links to child nodes representing possible next characters in words.

2. Step 2: Compare options with Trie node purpose

   Only To store characters and links to child nodes representing prefixes correctly describes storing characters and child links for prefixes.

3. Final Answer:

   To store characters and links to child nodes representing prefixes -> Option B

4. Quick Check:

   Trie node = character + child links [OK]

Hint: Trie nodes hold characters and children, not full words [OK]

Common Mistakes:

• Thinking Trie nodes store full words
• Confusing Trie nodes with linked list nodes
• Assuming Trie nodes store only integers

2. Which of the following is the correct way to declare a Trie node class with an array of 26 children nodes in Java?

easy

A. class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEnd; }

B. class TrieNode { TrieNode children = new TrieNode[26]; boolean isEnd; }

C. class TrieNode { TrieNode[] children = new TrieNode(); boolean isEnd; }

D. class TrieNode { TrieNode[] children = new TrieNode[25]; boolean isEnd; }

Solution

1. Step 1: Check array declaration syntax

   In Java, to declare an array of TrieNode objects, use TrieNode[] children = new TrieNode[26];

2. Step 2: Validate each option

   class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEnd; } correctly declares an array of 26 TrieNode references. Others have syntax errors or wrong sizes.

3. Final Answer:

   class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEnd; } -> Option A

4. Quick Check:

   Array of 26 children = correct declaration [OK]

Hint: Use TrieNode[] children = new TrieNode[26]; for English alphabets [OK]

Common Mistakes:

• Using single TrieNode instead of array
• Wrong array size (25 instead of 26)
• Incorrect array initialization syntax

3. What will be the output of the following Java code snippet?

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

public class Main {
    public static void main(String[] args) {
        TrieNode node = new TrieNode();
        System.out.println(node.children[0]);
        System.out.println(node.isEnd);
    }
}

medium

A. null
false

B. TrieNode@hashcode
true

C. null
true

D. Compilation error

Solution

1. Step 1: Understand default initialization of array elements

   In Java, an array of objects initializes elements to null by default.

2. Step 2: Check boolean default value

   Boolean isEnd is explicitly set to false, so it prints false.

3. Final Answer:

   null false -> Option A

4. Quick Check:

   Array elements null, boolean false by default [OK]

Hint: Uninitialized object arrays print null, booleans print false [OK]

Common Mistakes:

• Expecting children[0] to be a TrieNode instance
• Assuming boolean defaults to true
• Thinking code causes compilation error

4. Identify the error in the following TrieNode class definition and suggest the fix:

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

medium

A. children array size should be 25 instead of 26

B. isEnd should be initialized to true

C. children should be an array: TrieNode[] children = new TrieNode[26];

D. No error, code is correct

Solution

1. Step 1: Analyze children declaration

   The code declares children as a single TrieNode but tries to assign an array, which is invalid.

2. Step 2: Correct the declaration

   children should be declared as an array: TrieNode[] children = new TrieNode[26];

3. Final Answer:

   children should be an array: TrieNode[] children = new TrieNode[26]; -> Option C

4. Quick Check:

   Array declaration mismatch causes error [OK]

Hint: Declare children as TrieNode[] for arrays, not single TrieNode [OK]

Common Mistakes:

• Assigning array to single object variable
• Ignoring array syntax errors
• Assuming boolean needs initialization to true

5. You want to design a TrieNode class that supports lowercase English letters and efficiently checks if a node marks the end of a word. Which of the following is the best design choice?

hard

A. Use a String to store the full word at each node and a list of children nodes

B. Use an integer count of words passing through and no children array

C. Use a HashMap for children and no isEnd flag

D. Use a boolean isEnd flag and an array of 26 TrieNode children initialized to null

Solution

1. Step 1: Consider efficient storage for fixed alphabet

   For lowercase English letters, an array of size 26 is memory efficient and fast for indexing.

2. Step 2: Importance of isEnd flag

   The isEnd boolean marks if the node completes a word, essential for word recognition.

3. Final Answer:

   Use a boolean isEnd flag and an array of 26 TrieNode children initialized to null -> Option D

4. Quick Check:

   Array + isEnd flag = best for fixed alphabets [OK]

Hint: Use array + boolean flag for fixed alphabets, HashMap for dynamic sets [OK]

Common Mistakes:

• Storing full words at each node wastes memory
• Omitting isEnd flag loses word boundary info
• Using HashMap unnecessarily for fixed small alphabets