Recursive collection search

Question

I have a collection (List<Element>) of objects as described below:

class Element
{
  string Name;
  string Value;
  ICollection<Element> ChildCollection;
  IDictionary<string, string> Attributes;
}

I build a List<Element> collection of Element objects based on some XML that I read in, this I am quite happy with. How to implement searching of these elements currently has me, not stumped, but wondering if there is a better solution.

The structure of the collection looks something like this:

- Element (A)
  - Element (A1)
    - Element (A1.1)
  - Element (A2)
- Element (B)
  - Element (B1)
    - Element (B1.1)
    - Element (B1.2)
- Element (C)
  - Element (C1)
  - Element (C2)
  - Element (C3)

Currently I am using recursion to search the Attributes dictionary of each top level (A, B, C) Element for a particular KeyValuePair. If I do not find it in the top level Element I start searching its ChildElement collection (1, 1.1, 2, 2.1, n, etc.) in the same manner.

What I am curious about is if there is a better method of implementing a search on these objects or if recursion is the better answer in this instance, if I should implement the search as I am currently, top -> child -> child -> etc. or if I should search in some other manner such as all top levels first?

Could I, and would it be reasonable to use the TPL to search each top level (A, B, C) in parallel?

Answer 1

Recursion is one way of implementing a tree search where you visit elements in depth-first order. You can implement the same algorithm with a loop instead of recursion by using a stack data structure to store the nodes of your tree that you need to visit.

If you use the same algorithm with a queue instead of a stack, the search would proceed in breath-first order.

In both cases the general algorithm looks like this:

var nodes = ... // some collection of nodes
nodes.Add(root);
while (nodes.Count != 0) {
    var current = nodes.Remove ... // Take the current node from the collection.
    foreach (var child in current.ChildCollection) {
        nodes.Add(child);
    }
    // Process the current node
    if (current.Attributes ...) {
        ...
    }
}

Note that the algorithm is not recursive: it uses an explicit collection of nodes to save the current state of the search, whereas a recursive implementation uses the call stack for the same purpose. If nodes is a Stack<Element>, the search proceeds in depth-first order; if nodes is a Queue<Element>, the search proceeds in breadth-first order.

Answer 2

I grabbed this bit from SO somewhere, Its not mine but I cant provide a link to it. This class Flattens out a treeview for a recursive search, looks like it should do the same for you.

public static class SOExtension
{
    public static IEnumerable<TreeNode> FlattenTree(this TreeView tv)
    {
        return FlattenTree(tv.Nodes);
    }

    public static IEnumerable<TreeNode> FlattenTree(this TreeNodeCollection coll)
    {
        return coll.Cast<TreeNode>()
                    .Concat(coll.Cast<TreeNode>()
                                .SelectMany(x => FlattenTree(x.Nodes)));
    }
}

I found the link I got this from - its very easy to use. have a look. Is there a method for searching for TreeNode.Text field in TreeView.Nodes collection?

Answer 3

You can re-use existing components designed specifically for traversing in different ways, such as NETFx IEnumerable.Traverse Extension Method. It allows you to depth or breadth first. It lets you traverse an enumerable tree, depth or breadth first.

Example to get a flattened enumerable of directories:

IEnumerable<DirectoryInfo> directories = ... ;

IEnumerable<DirectoryInfo> allDirsFlattened = directories.Traverse(TraverseKind.BreadthFirst, dir => dir.EnumerateDirectories());

foreach (DirectoryInfo directoryInfo in allDirsFlattened)
{
    ...
}

For BreadhFirst it uses Queue<T> internally and for DepthFirst it uses Stack<T> internally.

It is not traversing nodes parallell and unless the traversal is resource demanding it isn't appropriate to use parallellism at this level. But that depends on the context.