Searching for nodes in a huge tree

Question

This is supposed to search for a node in a huge Treeview. The node could be found in many places. In other words there may be many nodes and the resulting tree should be expanded depending on where nodes are found.

I was asked to avoid recursivity in this method. The only solution I was able to get is using LINQ queries but I cannot since we are under 2.0 framework.

Can I avoid recursivity in this method?

  private void CheckFoundTreeNode(TreeNode startingTreeNode, List<Item> parentItems, ItemNode foundItemNode)
    {
        foreach (TreeNode childTreeNode in startingTreeNode.Nodes)
        {
            ItemNode itemNode = TreeBuilder.GetItemNode(childTreeNode);
            Item item = itemNode.Item;

            bool isParent;
            if (item.Ancestor == null)
                isParent = parentItems.Contains(item);
            else
            {
                Item ancestor = ((Grammar)item).DirectAncestor;
                isParent = parentItems.Contains(ancestor);
            }

            if (isParent)
            {
                childTreeNode.Expand();
                CheckFoundTreeNode(childTreeNode, parentItems, foundItemNode);
            }

            else if (itemNode == foundItemNode)
            {
                startingTreeNode.Expand();
                m_ListOfFoundNodes.Add(childTreeNode);
            }
        }
    }

Answer 1

The simplest way to avoid the recursive traversal is to have two lists: nodes you want to visit and nodes you have visited. Your loop then goes like this:

1. take a node from the 'to visit' list, or end if empty
2. check the node
3. add any connected nodes that aren't in the 'visited' list to the 'to visit' list

Answer 2

This looks like a very nice implementation. An iterative solution (without linq) would only serve to obfuscate the code in my opinion. I've found that when working with trees, recursion is a much cleaner and understandable method.

At first I thought about suggesting that you change the method from void to returning a list, but I think that would be less efficient than this.

The only thing I can really note is that you should always use braces. It will prevent future bugs.

        if (item.Ancestor == null)
            isParent = parentItems.Contains(item);
        else
        {
            Item ancestor = ((Grammar)item).DirectAncestor;
            isParent = parentItems.Contains(ancestor);
        }