Auto-complete using Trie

README.txt

This problem was asked by Twitter.

Implement an autocomplete system. 
That is, given a query string s and a set of all possible query strings,
return all strings in the set that have s as a prefix.

For example, given the query string de and the set of 
strings [dog, deer, deal], return [deer, deal].

Program.cs

class Program
{
    static void Main(string[] args)
    {
        Trie trie = new Trie();
        trie.Insert("dog");
        trie.Insert("deer");
        trie.Insert("deal");

        var foundWords = trie.Search("de");
        foreach (var item in foundWords)
        {
            Console.WriteLine(item); // deal, deer
        }
    }
}

class Trie
{
    private Node root;

    public Trie()
    {
        this.root = new Node();
    }

    public void Insert(string s)
    {
        var node = this.root;
        foreach (char ch in s)
        {
            if (node[ch] == null)
            {
                node[ch] = new Node();
            }
            node = node[ch];
        }
        node.IsEnd = true;
    }

    public IEnumerable<string> Search(string s)
    {
        var node = this.root;
        foreach (var ch in s)
        {
            if (node[ch] == null)
            {
                return Enumerable.Empty<string>();
            }
            node = node[ch];
        }
        return StringsInNode(s, node, new StringBuilder());
    }

    private IEnumerable<string> StringsInNode(string prefix, Node node, StringBuilder stringBuilder)
    {
        foreach (Tuple<char, Node> tuple in node)
        {
            var ch = tuple.Item1;
            var childNode = tuple.Item2;

            if (childNode.IsEnd)
            {
                // we find a string!
                yield return prefix + stringBuilder.ToString() + ch;
            }

            // explore child nodes to find strings
            stringBuilder.Append(ch);
            foreach (var stringsInSubNodes in StringsInNode(prefix, childNode, stringBuilder))
            {
                yield return stringsInSubNodes;
            }

            // child nodes have been explored!
            stringBuilder.Remove(stringBuilder.Length - 1, 1);
        }
    }
}

class Node : IEnumerable<Tuple<char, Node>>
{
    private Node[] nodes;
    internal bool IsEnd { get; set; }
    private static readonly int AlphabetSize = 'z' - 'a' + 1;

    internal Node()
    {
        this.nodes = new Node[AlphabetSize];
    }

    public Node this[char ch]
    {
        get 
        {
            return this.nodes[ch - 'a'];
        }
        set 
        {
            this.nodes[ch - 'a'] = value;
        }
    }

    public IEnumerator<Tuple<char, Node>> GetEnumerator()
    {
        for (int i = 0; i < this.nodes.Length; i++)
        {
            if (this.nodes[i] != null)
            {
                yield return new Tuple<char, Node>((char)('a' + i), this.nodes[i]);
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}