Trie Node Design and Initialization in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie node and what does it represent in a Trie data structure?

A Trie node represents a single character in a string. It stores links to child nodes for possible next characters and a flag to mark if it ends a valid word.

beginner

How do you initialize the children of a Trie node in Java?

You create an array of Trie nodes with size equal to the alphabet size (e.g., 26 for lowercase letters). Initially, all children are set to null.

beginner

Why do we use a boolean flag in a Trie node?

The boolean flag marks if the node represents the end of a valid word stored in the Trie.

beginner

Show the Java code snippet to declare a Trie node class with children and end-of-word flag.

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

beginner

What is the purpose of setting all children to null during Trie node initialization?

Setting children to null means no child nodes exist yet for those characters. It helps to check if a path exists when searching or inserting words.

What does each child in a Trie node's children array represent?

A The parent node

B A possible next character in a word

C The frequency of the word

D The length of the word

Each child corresponds to a possible next character in the stored words.

What is the size of the children array in a Trie node for lowercase English letters?

A 26

B 52

C 10

D 128

There are 26 lowercase English letters, so the array size is 26.

What does the boolean flag in a Trie node indicate?

A If the node is the root

B If the node is empty

C If the node has children

D If the node marks the end of a word

The flag marks if the node represents the end of a valid word.

What is the initial value of each child in the children array after Trie node initialization?

A false

B 0

C null

D new TrieNode()

Children are initially null, meaning no child nodes exist yet.

Which of these is NOT part of a typical Trie node design?

A Pointer to parent node

B Boolean end-of-word flag

C Array of children nodes

D Character value stored in node

Usually, Trie nodes do not store a pointer to their parent.

Explain how a Trie node is designed and initialized in Java.

Think about how to represent each character and mark word endings.

Describe the role of the boolean flag and children array in a Trie node.

Consider how words are stored and recognized in a Trie.

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