Is there an accepted name for this type of enumerable operation?

Question

I often find myself needing to traverse trees of hierarchial objects and perform operations on each item along the way. Is there a generally accepted name for this kind of operation in the list comprehension vernacular? I ask because I remember first learning about python's zip function back before it had an equivalent in the .net framework and thinking it had an unusual but appropriate name.

Here are a couple of generalized methods that recurse up and down tree structures and yield each item as they're encountered.

public static IEnumerable<T> Ancestors<T>(T source, Func<T, T> selector)
{
    do
    {
        yield return source;
        source = selector(source);
    } while (!Equals(source, default(T)));
}

public static IEnumerable<T> Descendents<T>(T source,
                                            Func<T, IEnumerable<T>> selector)
{
    var stack = new Stack<T>();
    stack.Push(source);
    while (stack.Count > 0)
    {
        source = stack.Pop();
        yield return source;
        var items = selector(source);
        if (items != null)
        {
            foreach (var item in items)
            {
                stack.Push(item);
            }
        }
    }
}

Answer 1

Assuming that the selector gives the child nodes, your second method is a "right first depth first" traversal. That is, if you had

      A
    /  \
   B     C
  / \   / \
 D   E F   G

Then you get A, C, G, F, B, E, D. You get "G" before "B" because "depth first" goes as deep as it can before it tries another branch. In your particular example you'll get C before B because it prioritizes right over left.

If you changed it to

foreach (var item in items.Reverse())  

then you'd get a left-first-depth-first traversal, which is how most people think of depth first traversal.

If you changed the stack to a queue then it would become a "breadth first" traversal. A, B, C, D, E, F, G. You do an entire "level" at a time.

There are other traversals as well. Notice that depth-first and breadth-first searches both have the property that parent nodes come before child nodes. You can also have "post-order" traversals in which every node comes after its children.

Binary trees also have an "inorder" traversal. The inorder traversal of this tree is D, B, E, A, F, C, G. That is, every left child comes before all its ancestors, and every right child comes after all its ancestors. As an exercise, can you write an in-order traversal on a binary tree?