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

Trie Node Design and Initialization

📖 Scenario: Imagine you are building a simple phone directory app. To quickly find names starting with certain letters, you decide to use a Trie data structure. The first step is to design and create a Trie node that will hold each letter and links to next letters.

🎯 Goal: Create a Trie node class in C++ that can store links to child nodes for each letter of the English alphabet and a flag to mark the end of a word.

📋 What You'll Learn

Create a class named TrieNode

Add a boolean variable isEndOfWord to mark if the node represents the end of a word

Add an array of pointers named children of size 26 to hold child nodes for each lowercase English letter

Initialize isEndOfWord to false and all children pointers to nullptr in the constructor

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding Trie node design is important for roles involving text processing, search engines, and efficient data retrieval.

1

Create the TrieNode class with members

Create a class called TrieNode with a public boolean variable isEndOfWord and a public array of 26 TrieNode* pointers called children.

DSA C++

// Your code here to create class TrieNode with isEndOfWord and children array

Hint

Use class TrieNode and declare bool isEndOfWord and TrieNode* children[26] inside it.

2

Add a constructor to initialize members

Add a public constructor to TrieNode that sets isEndOfWord to false and initializes all elements of children array to nullptr.

DSA C++

class TrieNode {
public:
    bool isEndOfWord;
    TrieNode* children[26];

    // Add constructor here to initialize isEndOfWord and children
    // Your code here
};

Hint

Use a constructor TrieNode() and a for loop to set all children[i] to nullptr.

3

Create a TrieNode object

Create a variable called root of type TrieNode using the default constructor.

DSA C++

class TrieNode {
public:
    bool isEndOfWord;
    TrieNode* children[26];

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

// Create a TrieNode object named root
// Your code here

Hint

Declare TrieNode root; to create the root node.

4

Print the initial state of root node

Print the value of root.isEndOfWord and the value of root.children[0] to verify initialization.

DSA C++

class TrieNode {
public:
    bool isEndOfWord;
    TrieNode* children[26];

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

TrieNode root;

// Print root.isEndOfWord and root.children[0]
// Your code here

Hint

Use std::cout << root.isEndOfWord << std::endl; and std::cout << root.children[0] << std::endl; to print the values.