(C++) Please complete the bolded functions called "int numberOfCompletions(string prefix)" and "int numberOfStrings(node* p)" located in the trie.h header file.

//------------------------------------------------------------

//main.cpp

#include #include #include "trie.h"

using namespace std;

int main() { trie T; T.insert("ape"); T.insert("zoo"); T.insert("pie"); T.insert("ice"); T.insert("hat"); T.insert("apple"); T.insert("zebra"); T.insert("pumpkin"); T.insert("orange"); T.insert("bird");

T.display(); cout << T.num_of_words() << endl;

return 0; }

//------------------------------------------------------------

//trie.h

#pragma once #include #include using namespace std;

class trie { private: class node { public: bool marked; node* children[256];

node() { marked = false;

for (int i = 0; i < 256; i++) children[i] = nullptr; } };

node* root;

void display(node* p, string prefix) { if (p == nullptr) {

} else { if (p->marked) cout << prefix << endl;

for (int i = 0; i < 256; i++) { char c = i; display(p->children[i], prefix + c); } } }

//Return number of strings in given sub-trie int numberOfStrings(node* p) { }

public: trie() { root = new node(); }

//Return number completions of prefix within //the trie. int numberOfCompletions(string prefix) {

}

void insert(string s) { node* current = root; for (int i = 0; i < s.length(); i++) { if (current->children[s[i]] == nullptr) current->children[s[i]] = new node();

current = current->children[s[i]]; }

current->marked = true; }

int numStrings() { return numStrings(root); }

void display() { display(root, ""); } };