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.