Is this a reasonable Trie implementation?

Question

http://en.wikipedia.org/wiki/Trie

The basic idea is to support fast searches via prefix matching. In my implementation, I allow each node to store all of the words that match its given prefix, and then if the word length exceeds the length of the node's prefix, it passes the word into its children for further storage.

public class TrieNode
{
    private string Prefix { get; set; }
    private IList<string> Items { get; set; }
    private IDictionary<string, TrieNode> ChildNodes { get; set; }
    private IEqualityComparer<string> Comparer { get; set; }

    public TrieNode() : this(StringComparer.CurrentCulture) { }
    public TrieNode(IEqualityComparer<string> comparer) : this(comparer, string.Empty) { }

    private TrieNode(IEqualityComparer<string> comparer, string prefix)
    {
        if (prefix == null)
            throw new ArgumentNullException("Invalid prefix");

        this.Prefix = prefix;
        this.Items = new List<string>();
        this.ChildNodes = new Dictionary<string, TrieNode>(comparer);
        this.Comparer = comparer;
    }

    public void Add(string word)
    {
        if (word == null)
            throw new InvalidOperationException("Cannot add null to list");

        if (word.Length < this.Prefix.Length
            || !this.Comparer.Equals(word.Substring(0, this.Prefix.Length), this.Prefix))
        {
            throw new ArgumentException("Parameter does not match prefix.");
        } 

        this.Items.Add(word);

        if (word.Length > this.Prefix.Length)
        {
            string childKey = word.Substring(0, this.Prefix.Length + 1);
            if (!this.ChildNodes.ContainsKey(childKey))                
            {
                this.ChildNodes.Add(childKey, new TrieNode(this.Comparer, childKey));                    
            }

            this.ChildNodes[childKey].Add(word);
        }
    }

    public void AddRange(IEnumerable<string> words)
    {
        foreach (string word in words)
            this.Add(word);
    }

    public ReadOnlyCollection<string> FindMatches(string searchPrefix)
    {
        if (searchPrefix == null)
            throw new InvalidOperationException("Cannot search on null strings");

        if (this.Comparer.Equals(searchPrefix, this.Prefix))
        {
            return new ReadOnlyCollection<string>(this.Items);
        }
        else
        {
            string childKey = searchPrefix.Substring(0, this.Prefix.Length + 1);
            if (this.ChildNodes.ContainsKey(childKey))
                return this.ChildNodes[childKey].FindMatches(searchPrefix);
            else
                return new ReadOnlyCollection<string>(new string[0]); // empty list for no matches 
        }
    }
}

...

TrieNode trie = new TrieNode(StringComparer.CurrentCultureIgnoreCase);
trie.AddRange(new string[] { "Apple", "Banana", "BANANA", "Bar", "Berry", "Cherry", "Coconut", "Date" });

ReadOnlyCollection<string> matches = trie.FindMatches("BA"); // BANANA, banana, Bar

The slight concern I have is that each node contains its list of matching words, it's not an aggregation from its children. I call it slight, because it allows for easy logic when performing searches, as once a match is found, there's no need to further poll children and aggregate responses. On the other hand, I end up storing the same word in n lists, where n is the length of the word.

Edit An answer suggested returning an IEnumerable<string> to allow lazy streaming of results as well as to eliminate unnecessary copying. The tradeoff is that ordering is not preserved, and the code logic (at least, the way I tried it) is a bit less simple. But the quick changes I made to allow such a sequence are the following. First, inside the Add method, only storing matches to the specific prefix

if (this.Comparer.Equals(word, this.Prefix))
{
    // keep each match - preserves number of matches as well as differences 
    // if the comparer allows insensitive equality
    this.Items.Add(word); 
}

And then the FindMatches method

public IEnumerable<string> FindMatches(string searchPrefix)
{
    if (searchPrefix == null)
        throw new InvalidOperationException("Cannot search on null strings");

    if (this.Comparer.Equals(searchPrefix, this.Prefix))
    {
        return this.Items.Concat(this.ChildNodes.SelectMany(n => n.Value.FindMatches(n.Key)));
    }
    else
    {
        string childKey = searchPrefix.Substring(0, this.Prefix.Length + 1);
        if (this.ChildNodes.ContainsKey(childKey))
        {
            return this.ChildNodes[childKey].FindMatches(searchPrefix);
        }
        else
        {
            return Enumerable.Repeat(string.Empty, 0);
        }
    }
}

Answer 1

Instead of returning a collection, why not return an IEnumerable? Then you would perform no list copying, and it would be low cost to return an Enumerable that actually recurses through all the children lists.

Answer 2

Consider just storing a single character at each node. Currently, you are storing this:

given abc, abdfa, abdfb, bcd, efg

a : abc, abdfa, abdfb
. ab : abc, abdfa, abdfb
.. abc : abc
.. abd : abdfa, abdfb
b : bcd
. bc : bcd
.. bcd : bcd
e : efg
. ef : efg
.. efg : efg

However, just storing the character and a boolean for whether the cumulative prefix has been found:

a : F
. b : F
.. c : T
.. d : F
... f : F
.... a : T
.... d : T
b : F
. c : F
.. d : T
e : F
. f : F
.. g : T

Thus your add code would be:

public void Add(string wordExcess)
{
    /* validation etc here */

    if (wordExcess == "")
        this.Seen = true;
    else
    {
        // child key is just a char
        string childKey = wordExcess[0];
        if (!this.ChildNodes.ContainsKey(childKey))                
            this.ChildNodes.Add(childKey, new TrieNode(this.Comparer, childKey));                    

        string childExcess = wordExcess.Substring(1,wordExcess.Length-1);
        this.ChildNodes[childKey].Add(childExcess);
    }
}

Then iterating to find matches:

public IEnumerator FindMatches(string searchExcess)
{
    /** validation etc here **/

    if (searchExcess == "" && this.Seen)
        yield return this.Prefix;

    if (searchExcess.Length > 0)
    {
        string childKey = searchExcess[0];
        if (this.ChildNodes.ContainsKey(childKey))
        {
            string childExcess = searchExcess.Substring(1,childExcess.Length-1);
            foreach(string match in this.ChildNodes[childKey].FindMatches(searchExcess)
                yield return this.Prefix+match;
        }
    }
    else
    {
        foreach(KeyValuePair <string,TrieNode> pair in this.ChildNodes)
            foreach(string match in pair.Value.FindMatches(""))
                yield return this.Prefix+match;
    }
}

Here we are appending the current prefix to the matches as you return them, and a parent call will do the same. So the a.b.c.d node matches "" and returns "d" to the c.match, which returns "c"+"d" to the b.match which returns "b"+"cd" etc.