Trie Node Design and Initialization in DSA C# - Build from Scratch

Trie Node Design and Initialization

📖 Scenario: Imagine you are building a simple phone contact search feature. To do this efficiently, you want to create a Trie data structure. The first step is to design and initialize the basic building block: the Trie Node.

🎯 Goal: Create a TrieNode class in C# that can hold children nodes for each letter and a flag to mark the end of a word.

📋 What You'll Learn

Create a class called TrieNode

Add a public array of TrieNode called children with size 26 (for letters a-z)

Add a public boolean variable called isEndOfWord initialized to false

Create a constructor that initializes children array and sets isEndOfWord to false

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and spell checkers to quickly find words or prefixes.

💼 Career

Understanding Trie nodes is important for roles involving text processing, search optimization, and building efficient data structures.

1

Create the TrieNode class

Create a public class called TrieNode.

DSA C#

// Your code here

Hint

Start by defining a public class named TrieNode.

2

Add children array and isEndOfWord flag

Inside the TrieNode class, add a public array of TrieNode called children with size 26, and a public boolean variable called isEndOfWord initialized to false.

DSA C#

public class TrieNode
{
    // Your code here
}

Hint

Use new TrieNode[26] to create the children array and set isEndOfWord to false.

3

Add constructor to initialize children and isEndOfWord

Add a public constructor to the TrieNode class that initializes the children array with size 26 and sets isEndOfWord to false.

DSA C#

public class TrieNode
{
    public TrieNode[] children = new TrieNode[26];
    public bool isEndOfWord = false;

    // Your code here
}

Hint

Define a constructor with the same name as the class and initialize the fields inside it.

4

Print initial state of a new TrieNode

Create a new TrieNode object called node and print the value of node.isEndOfWord.

DSA C#

public class TrieNode
{
    public TrieNode[] children;
    public bool isEndOfWord;

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

// Your code here

Hint

Create an instance of TrieNode and print isEndOfWord to check it is false.

Practice

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

easy

A. To act as a queue for BFS traversal

B. To store integer values for sorting

C. To hold a single string value only

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

Solution

1. Step 1: Understand Trie node role

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

2. Step 2: Compare options

   Only To store characters and links to child nodes representing prefixes correctly describes this role; others describe unrelated data structures or incorrect uses.

3. Final Answer:

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

4. Quick Check:

   Trie node = store chars + children links [OK]

Hint: Trie nodes hold chars and children links [OK]

Common Mistakes:

• Thinking Trie nodes store full words only
• Confusing Trie nodes with array or list nodes
• Assuming Trie nodes hold integer values

2. Which of the following is the correct way to declare a Trie node class with a children array for 26 lowercase letters in C#?

easy

A. public class TrieNode { public TrieNode[] children = new TrieNode[26]; public bool isEndOfWord; }

B. public class TrieNode { public List<char> children = new List<char>(); public bool isEndOfWord; }

C. public class TrieNode { public Dictionary children = new Dictionary(); public bool isEndOfWord; }

D. public class TrieNode { public TrieNode children = null; public bool isEndOfWord; }

Solution

1. Step 1: Identify correct children storage

   For 26 lowercase letters, an array of size 26 is standard to store child nodes indexed by character.

2. Step 2: Check syntax correctness

   public class TrieNode { public TrieNode[] children = new TrieNode[26]; public bool isEndOfWord; } declares a TrieNode array of size 26 and a boolean flag, which is correct syntax and design.

3. Final Answer:

   public class TrieNode { public TrieNode[] children = new TrieNode[26]; public bool isEndOfWord; } -> Option A

4. Quick Check:

   Children array size 26 = public class TrieNode { public TrieNode[] children = new TrieNode[26]; public bool isEndOfWord; } [OK]

Hint: Use TrieNode[] children = new TrieNode[26] for letters [OK]

Common Mistakes:

• Using List<char> instead of TrieNode array
• Using Dictionary unnecessarily
• Declaring children as single TrieNode instead of array

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

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

public class Program {
    public static void Main() {
        TrieNode node = new TrieNode();
        Console.WriteLine(node.children[0] == null);
        Console.WriteLine(node.isEndOfWord);
    }
}

medium

A. false
False

B. true
True

C. true
False

D. false
True

Solution

1. Step 1: Check default initialization of children array

   In C#, arrays of reference types initialize elements to null by default, so children[0] is null, making the first print true.

2. Step 2: Check default value of isEndOfWord

   isEndOfWord is explicitly set to false, so printing it outputs false.

3. Final Answer:

   true False -> Option C

4. Quick Check:

   children[0] null = true, isEndOfWord false = false [OK]

Hint: Reference arrays default to null, bool defaults to false [OK]

Common Mistakes:

• Assuming children array elements are initialized to new nodes
• Confusing default bool value as true
• Misreading array initialization behavior

4. Identify the error in the following TrieNode class code and select the fix:

public class TrieNode {
    public TrieNode[] children;
    public bool isEndOfWord;

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

medium

A. Remove constructor and initialize fields inline

B. Change array size from 25 to 26 to cover all lowercase letters

C. Declare children as List<TrieNode> instead of array

D. Initialize isEndOfWord to true in constructor

Solution

1. Step 1: Check children array size

   For 26 lowercase English letters, children array must be size 26, not 25.

2. Step 2: Evaluate other options

   isEndOfWord should start false; List is optional but not required; constructor is fine.

3. Final Answer:

   Change array size from 25 to 26 to cover all lowercase letters -> Option B

4. Quick Check:

   Children array size must be 26 [OK]

Hint: Children array size must match alphabet count (26) [OK]

Common Mistakes:

• Using wrong array size causing index errors
• Setting isEndOfWord true by default
• Unnecessarily changing data structure type

5. You want to design a TrieNode class that supports both lowercase and uppercase English letters (52 total). Which is the best way to initialize the children array in C#?

hard

A. public Dictionary children = new Dictionary(); // dynamic keys for all letters

B. public TrieNode[] children = new TrieNode[26]; // only lowercase letters supported

C. public TrieNode[] children = new TrieNode[52]; // index 0-25 for 'a'-'z', 26-51 for 'A'-'Z'

D. public List<TrieNode> children = new List<TrieNode>(52); // list with capacity 52

Solution

1. Step 1: Consider fixed array size for 52 letters

   Using a fixed array of size 52 is possible but requires careful indexing and is error-prone.

2. Step 2: Evaluate dynamic dictionary approach

   A Dictionary with char keys allows flexible, clear mapping for both uppercase and lowercase letters without manual indexing.

3. Final Answer:

   public Dictionary children = new Dictionary(); // dynamic keys for all letters -> Option A

4. Quick Check:

   Dictionary best for mixed case letters [OK]

Hint: Use Dictionary for mixed letter sets [OK]

Common Mistakes:

• Using fixed array without clear indexing for uppercase
• Using List without key mapping
• Ignoring uppercase letters support