Trie data structure (part -1): Basics

The TrieNode class is a helper class used to implement the trie data structure. Each TrieNode represents a node in the trie and contains the following two fields:

class TrieNode {
public:
    bool is_word;
    std::unordered_map<char, TrieNode*> children;

    TrieNode() : is_word(false) {}
};

• is_word: a boolean flag indicating whether the path from the root to this node represents a complete word in the trie.
• children: an unordered map that maps each character to the child node corresponding to that character.

Here’s a breakdown of each field:

is_word

The is_word field is a boolean flag that is set to true if the path from the root to this node represents a complete word in the trie. For example, if we insert the word "cat" into the trie, then the is_word flag will be set to true for the nodes corresponding to the characters 'c', 'a', and 't' in the trie.

children

The children field is an unordered map that maps each character to the child node corresponding to that character. For example, if we insert the words "cat" and "car" into the trie, then the 'c' node will have two children nodes: one for the character 'a' and one for the character 'r'. Each of these child nodes will in turn have their own children nodes corresponding to subsequent characters in the words.

Here’s an example of how a TrieNode might be used to represent the words "cat" and "car" in the trie:

    root
    /  \
   c    *
  / \
 a   r
 |   |
 t   *

In this example, the root node has two child nodes: one for the character ‘c’ and one for the special character ‘’ (which is used to indicate the end of a word). The ‘c’ node has two child nodes: one for the character ‘a’ and one for the character ‘r’. The ‘a’ node has one child node for the character ‘t’, and the ‘r’ node has one child node for the character ‘’, indicating the end of the word “car”.