Basic prefix tree implementation question

Question

I've implemented a basic prefix tree or "trie". The trie consists of nodes like this:

// pseudo-code
struct node {
    char c;
    collection<node> childnodes;
};

Say I add the following words to my trie: "Apple", "Ark" and "Cat". Now when I look-up prefixes like "Ap" and "Ca" my trie's "bool containsPrefix(string prefix)" method will correctly return true.

Now I'm implementing the method "bool containsWholeWord(string word)" that will return true for "Cat" and "Ark" but false for "App" (in the above example).

Is it common for nodes in a trie to have some sort of "endOfWord" flag? This would help determine if the string being looked-up was actually a whole word entered into the trie and not just a prefix.

Cheers!

Answer 1

If you need to store both "App" and "Apple", but not "Appl", then yes, you need something like an endOfWord flag.

Alternatively, you could fit it into your design by (sometimes) having two nodes with the same character. So "Ap" has to childnodes: The leaf node "p" and an internal node "p" with a child "l".

Answer 2

The end of the key is usually indicated via a leaf node. Either:

• the child nodes are empty; or
• you have a branch, with one prefix of the key, and some children nodes.

Your design doesn't have a leaf/empty node. Try indicating it with e.g. a null.