In a previous post we started with some motivation for the need of a tree like data structure for efficient prefix matching. We will see how to implement Trie in C++ in this post.

Trie is a tree data structure made up of nodes that contain some data. So, we need to design a structure for the nodes and some structure fields for storing the data. Since we are talking about prefix strings and strings are made up of characters, we can think of a node as having a hashmap, storing the prefix character and a reference to the Trie node holding the remaining characters (children nodes). We can go about defining a structure like this:

struct Trie
{
  std::unordered_map<char, Trie*> lookup;
  bool isLeaf;
};

The boolean variable isLeaf is to indicate the end (leaf node) of the string in the Trie. And when we start populating a new Trie, we need to allocate a new structure, something like the following newTrieNode(). We set the isLeaf to false as we need to set this to true only for leaf nodes.

Trie* newTrieNode()
{
  Trie* node = new Trie;
  node->isLeaf = false;
  return node;
}

We can also write a small function to check if a node has any children (by checking the value of isLeaf).

bool hasChildren(Trie* const curr)
{
  for (auto it : curr->lookup)
    if (it.second != nullptr)
      return true;
  return false;
}

We will look at populating a Trie by inserting characters from a string into the Trie, as well as searching for a prefix in a future post.