Trie Node Design and Initialization in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Node Initialization

What is the output of the following C++ code that initializes a Trie node and prints its initial state?

DSA C++

struct TrieNode {
    bool isEndOfWord;
    TrieNode* children[26];
    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

#include <iostream>
int main() {
    TrieNode node;
    std::cout << node.isEndOfWord << " ";
    int count = 0;
    for (int i = 0; i < 26; i++) {
        if (node.children[i] == nullptr) count++;
    }
    std::cout << count << std::endl;
    return 0;
}

A 0 26

B 1 0

C 0 0

D 1 26

💡 Hint

Check the default values assigned in the constructor for isEndOfWord and children array.

The constructor sets isEndOfWord to false (which prints as 0) and initializes all 26 children pointers to nullptr. Counting the null pointers gives 26.

🧠 Conceptual

intermediate

Purpose of Children Array in Trie Node

What is the main purpose of the children array in a Trie node?

A To keep track of the parent node of the current node

B To store the frequency of words ending at this node

C To store pointers to child nodes representing each possible character

D To store the actual characters of the word at this node

💡 Hint

Think about how a Trie branches for each letter.

The children array holds pointers to child nodes for each character (usually 26 for lowercase English letters). This allows branching to next letters in stored words.

🔧 Debug

advanced

Identify the Bug in Trie Node Initialization

What error will occur when running this Trie node constructor code?

DSA C++

struct TrieNode {
    bool isEndOfWord;
    TrieNode* children[26];
    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i <= 26; i++) {
            children[i] = nullptr;
        }
    }
};

A Logical error: isEndOfWord not initialized

B No error, code runs correctly

C Compilation error due to missing semicolon

D Runtime error due to out-of-bounds array access

💡 Hint

Check the loop boundary condition for the children array initialization.

The loop uses i <= 26 which accesses index 26, but valid indices are 0 to 25. This causes out-of-bounds access leading to runtime error.

📝 Syntax

advanced

Correct Syntax for Trie Node Constructor Initialization

Which option correctly initializes all children pointers to nullptr in the TrieNode constructor?

DSA C++

struct TrieNode {
    bool isEndOfWord;
    TrieNode* children[26];
    TrieNode() {
        isEndOfWord = false;
        // Initialize children
    }
};

A for (int i = 0; i < 26; i++) children[i] = nullptr;

B for int i = 0; i < 26; i++ children[i] = nullptr;

C for (int i = 0; i <= 26; i++) children[i] = nullptr;

D for (int i = 1; i < 26; i++) children[i] = nullptr;

💡 Hint

Check for correct for-loop syntax and valid array indices.

Option A uses correct syntax and valid indices 0 to 25. Option A misses parentheses. Option A accesses index 26 (invalid). Option A skips index 0.

🚀 Application

expert

Number of Nodes After Inserting Words in Trie

Given the following insertions into an empty Trie, how many Trie nodes exist after inserting the words "cat", "car", and "dog"?

DSA C++

struct TrieNode {
    bool isEndOfWord;
    TrieNode* children[26];
    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) children[i] = nullptr;
    }
};

// Insert words: "cat", "car", "dog"

A 6

B 8

C 7

D 9

💡 Hint

Count nodes shared by common prefixes only once.

"cat" and "car" share 'c' and 'a' nodes, so those nodes are shared. The nodes are:
Root (1)
c (2)
a (3)
t (4) for "cat"
r (5) for "car"
d (6) for "dog"
o (7) for "dog"
g (8) for "dog"
Total nodes = 8.