How to Print Out the Words In a Trie With a Vector Given a Particular Prefix

Question

I am currently working on a project in which I need to print out the words in a trie that match a given prefix, given by a user using a string vector to print out the words. However, I am having trouble getting started with this, and would love any suggestions that you guys could give me.

This is an example of what I mean

Words in trie { app, address, add, beg, cow, mice} prefix given ad using a vector to print out words that contain the prefix ad: address add

Thank you very much for any help that you provide.

Answer 1

First things first, a trie is a tree.

In a trie, all words with a given prefix (say ad) are actually stored in the subtree of your trie that is accessed when searching for the prefix ad.
So to print all words in your trie that have a given prefix is done in 2 steps:

1. Find the node node corresponding to your prefix
2. List all the word in the subtree rooted in node.

Here is a pseudocode:

find_all_words_starting_with(string prefix, trieNode node, int depth){
    if (depth == length(prefix)){
        suffix = empty_string
        print_all_words_with_prefix(prefix, suffix, node)
    } else {
        letter = prefix[depth]
        if (node.hasChild(letter)){
            find_all_words_starting_with(prefix, node.getChild(letter), depth+1)
        } else { // no word with the correct prefix
            return
        }
    }
}

print_all_words_with_prefix(prefix, suffix, node){
    if (node.isCompleteWord){
        print(prefix + suffix)
    }
    for each letter c in the alphabet {
        if (node.hasChild(c)){
            print_all_words_with_prefix(prefix, suffix + c, node.getChild(c))
        }
    }
}

find_all_words_starting_with does the first part of the job. It find the node corresponding to the prefix, and calls the second function, print_all_words_with_prefix, that will print all the complete words in the subtree.