CareerCup

You can use the dictionary data structure to store the words of the dictionary.

Node* construct_tree() {
  // left means matching, right means not matching
  Node* root = new Node("AP");
  root->left = new Node("APP");
  root->left->left = new Node("APPLE");
  root->left->right = new Node("APE");
  root->right = new Node("B");
  root->right->left = new Node("BAB");
  root->right->left->left = new Node("BABY");
  root->right->left->right = new Node("BALL");
  root->right->right = new Node("CAT");
}

vector<string> find_matches(string str, Node* root) {
  Node* last = NULL;
  Node* curr = root;
  // Find the last matching node 
  while (curr) {
    int min_len = min(str.length(), curr->str.length());
    bool str_eq = str.substr(0, min_len).compare(0, curr->str.substr(min_len)) == 0;
    bool too_long = str.length <= curr->str.length();
    if (str_eq && too_long) { last = curr; break; }
    else if (str_eq) { last = curr; curr = curr->left; }
    else curr = curr->right;
  }
  // Now collect all the leaves under last
  vector<string> matches;
  queue<Node*> nodes;
  nodes.push(last);
  while (nodes.size() > 0) {
    Node* n = nodes.pop();
    if (!n->left && !n->right) matches.push_back(n->str);
    if (n->left) nodes.push(n->left);
    if (n->right) nodes.push(n->right); 
  }
  return matches;
}

One should ask, will we necessarily have only 5 words. In that case I would use simple string matching
On the other hand, if the number of words are large, I will use a Trie.