Returning multiple nodes when searching a tree/trie?

Question

I have constructed a suffix trie, a tree containing all the suffixes of a string, where each node contains only one character, with a SuffixNode at the end of each path which contains the locations of the suffixes within the string.

Let's say my trie contains the words, "Cat", "Car" and "Can" and I want to search for "Ca", the result should return 3 suffix nodes since the search string is found in 3 different places. I managed to search the tree for "Ca", but once I reach that point, I don't know how to continue traversing the children of the 'a' node to find all the suffix nodes.

I was thinking of using some sort of collection to add the suffix nodes to and then return the collection. Does this approach make sense, or are there better solutions?

I have solved the searching problem below. The reason it wasn't returning any nodes has to do with the creation of the tree and the differences between nodes:

public void SearchTrie(Node parent, String s, List<SuffixNode> suffixes)
    {
        Node n = FindNode(parent, s);
        FindSuffixes(n, suffixes);
    }

    private void FindSuffixes(Node parent,List<SuffixNode> suffixes)
    {            
        if (parent is SuffixNode)
        {
            suffixes.Add((SuffixNode)parent);
        }
        else
        {
            foreach (KeyValuePair<char, Node> child in parent.children)
            {
                FindSuffixes(child.Value, suffixes);
            }
        }
    }

    private Node FindNode(Node parent, String s)
    {
        if ((s.Length == 1) && parent.children.ContainsKey(s[0]))
        {
            Node n = parent.children[s[0]];
            return n;
        }

        while (s[0].ToString() != "")
        {
            if (parent.children.ContainsKey(s[0]))
            {
                if ((s.Length > 1))
                {
                    return FindNode(parent.children[s[0]], s.Substring(1));
                }

            }
            else
            {
                break;
            }

        }

        return null;
    }

Node:

class Node
{
    public char label;
    public Node parent;
    public Dictionary<char,Node> children;

    public Node(Node NewParent, char NewLabel)
    {
        this.parent = NewParent;
        this.label = NewLabel;
        children=new Dictionary<char,Node>();
    }
}

Answer 1

I was thinking of using some sort of collection to add the suffix nodes to and then return the collection.

That would be the first choice.

..., or are there better solutions?

There are other solutions, like

• filling a list supplied by the caller
• use an iterator block with yield return

But w/o any special requirements, fill a List<string> and return it as IEnumerable<string>.