Trie Data Structure (Prefix Tree)

Use a TrieNode class that has a next member which is an array of 26 TrieNode pointers that represents a pointer to TreeNode object for each of 26 letters in the alphabet. We initialise these TrieNode pointers to NULL. We also have a bool member wordEnd initialised to false. An alternative, solution would be to use a hash map rather than vector to contain the next TrieNode pointers, which could contain a wider range of character sets.

class TrieNode {
public:
    vector next;
    bool wordEnd;
    TrieNode() : next(26, NULL), wordEnd(false) {};
};

We can then create a Trie class which will wrap the root TrieNode and a set of methods.
The Trie constructor creates a root TrieNode pointer member.
The Insert method steps through letters of the word, creating TrieNode objects and pointers in next as we go. Finally it sets wordEnd on the last letter.
The Search method goes through each letter in the word traversing through TrieNodes and returns wordEnd state on the final letter.
StartsWith is similar to search but it does not need the wordEnd check. I also created destructor that deleted all the TrieNode objects recursively.