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!

score 2 · Answer 1 · answered Jun 14 '11 at 20:17

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.

answered Jun 14 '11 at 20:17

Don Stewart

137,316
36
365
468

Thanks for the response. However I did try indicating leaf nodes by checking the empty childnodes collection (like you mentioned). This doesn't solve the following problem: insert "Apple" into the trie. Insert "Appl" into the trie. Ask if "Apple" is a whole word. In this example it is (assuming you check leaf nodes using a method mentioned above) However asking if "Appl" is a whole word incorrectly returns false since "l" is not a leaf node. Adding the "endOfWord" flag fixes this. – MrDatabase Jun 14 '11 at 20:49

score 1 · Accepted Answer · answered Jun 15 '11 at 12:03

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".

Basic prefix tree implementation question

2 Answers2