Click here to Skip to main content
13,347,998 members (70,261 online)
Click here to Skip to main content
Add your own
alternative version


26 bookmarked
Posted 20 Feb 2008

Apply "yield return" recursively - iterating tree data structures

, 21 Feb 2008
Rate this:
Please Sign up or sign in to vote.
A generic function that enables "deep-iterating" the leafs of arbitrary tree data structures simply using foreach.


"Tree-data structures" are very commonly used (e.g.: XML, Directory system, Forms.ControlCollection). They are very powerful, but a little unhandy:

  • you cannot enumerate them by foreach. For each action you want to execute on each tree-leaf you have to implement a specialized recursive method.
  • its not trivial to leave the recursive execution before it reaches its natural end.
  • passing some arguments (e.g. search-patterns of a recursive search) blows out the function-stack.

How nice it would be if one could do a "deep-iteration" of the tree-leafs using a simple foreach!

  • no more recursive functions
  • leave the "recursion" with "break"
  • the leafs come to the search-patterns, not the other way round: injecting search-patterns into recursive calls.

We can do this, and it is not that complicated:

public static class Recurser<TItem, TCollection> 
       where TCollection : IEnumerable {

  private static MethodInfo _GetChilds;
  // ...
  public static IEnumerable<TItem> TopDown(TCollection Coll) {
     foreach (TItem Itm in Coll) {
        yield return Itm;
        TCollection Coll2 = (TCollection)_GetChilds.Invoke(Itm, null);
        foreach (TItem Itm2 in TopDown(Coll2)) { yield return Itm2; }

Why the hack is it called "TopDown"? Ha, because I've done a "BottomUp" too ;):

public static IEnumerable<TItem> BottomUp(TCollection Coll) {
 foreach (TItem Itm in Coll) {
    TCollection Coll2 = (TCollection)_GetChilds.Invoke(Itm, null);
    foreach (TItem Itm2 in BottomUp(Coll2)) { yield return Itm2; }
    yield return Itm;

"TopDown" first yields the root-items, later the ... (more explanation not needed, I think).

Then, the only open question should be: "how to get _GetChilds?" I've got it using a Reflection-"investigation" of the types "TItem" and "TCollection". Such "investigations" are very slow operations - for that, I do them only once per "generic shape" of the Recurser. Namely in the static constructor:

static Recurser() {
    // since Reflection is very slow, this static constructor will be
    // executed only once per generic shaping
    Type tpItm = typeof(TItem);
    Type tpColl = typeof(TCollection);
    const BindingFlags BindFlags = BindingFlags.Public | BindingFlags.Instance;
    foreach (MemberInfo mi in tpItm.GetMembers(BindFlags)) {
        MethodInfo Proposed = null;
        switch (mi.MemberType) {
           case MemberTypes.Property:
              PropertyInfo p = (PropertyInfo)mi;
              if (p.PropertyType == tpColl) {
                 Proposed = p.GetGetMethod();
           case MemberTypes.Method:
              MethodInfo m = (MethodInfo)mi;
              if (m.ReturnType == tpColl) {
                 Proposed = m;
        if (Proposed.GetParameters().Length == 0) {
           _GetChilds = Proposed;
    throw new ArgumentException(string.Concat("can't find a " + 
       "recursive member in ", tpItm.Name, "!"));

Using the Code

Here, we have three "deep-iterations": iterate the TreeNodes, DirectoryInfos, and Controls on a Form:

using System;
using System.Drawing;
using System.Windows.Forms;
using System.Collections.Generic;
// To declare a generic shape of Recurser causes a quite long codeline.
// For that I prefer to pull it together in an using-statement
using Allnodes = Globals.Recurser<System.Windows.Forms.TreeNode,
using AllDirs = Globals.Recurser<System.IO.DirectoryInfo,
using AllControls = Globals.Recurser<System.Windows.Forms.Control,

namespace TreeIterations {
   public partial class frmMain : Form {

      public frmMain() {

      private void btTest_Click(object sender, EventArgs e) {
         WriteLine("Enumerating Treenodes from bottom upwards");
         foreach (TreeNode Nd in Allnodes.BottomUp(treeView1.Nodes)) {
            WriteLine("Depth: ", Allnodes.Depth, ", Name: ", Nd.ToString());
         WriteLine("Enumerating Directories TopDown");
         System.IO.DirectoryInfo Root = new System.IO.DirectoryInfo(@"..\..\");
         foreach (System.IO.DirectoryInfo DI in AllDirs.TopDown(Root)) {
            WriteLine("Depth: ", AllDirs.Depth, ", FullName: ", DI.FullName);
         WriteLine("Enumerating Controls TopDown");
         // call Recurser without using the useful "using AllControls" - Statement
         foreach (Control Ctl in Globals.Recurser
               <Control, Control.ControlCollection>.TopDown(this)) {
            // display tree indented
               new String(' ', AllControls.Depth * 2), 
               Ctl.GetType().Name, @" """, Ctl.Name, @"""");

      private void WriteLine(params object[] Segments) {

Maybe you've noticed: one of my secrets is, how the useful thing called "Depth" is implemented. You can find this out in the attached download ;)

Points of Interest

The methods "TopDown()" and "BottomUp()" are of data type "IEnumerable<TItem>". So in C# 3.0, they will support type-inferring, and also the wonderful LINQ stuff.

I was unsure about the "skill-level" I had to assign. To beginners, this is useful as a way of recursion in a simple foreach-manner. The functionality better fits for "intermediate" or "advanced" levels, because "yield return", static constructors, class-redefining with the using-statement, Reflection - those features seem to me not to be pure beginner-stuff.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Germany Germany
No Biography provided

You may also be interested in...

Comments and Discussions

General[My vote of 2] A better solution! Pin
Member 224161228-Aug-10 11:10
memberMember 224161228-Aug-10 11:10 
GeneralRe: [My vote of 2] A better solution! Pin
Mr.PoorEnglish28-Aug-10 11:49
memberMr.PoorEnglish28-Aug-10 11:49 
GeneralRe: [My vote of 2] A better solution! Pin
Member 224161230-Aug-10 3:59
memberMember 224161230-Aug-10 3:59 
GeneralVote 4: Stanford has a better solution running on n(O) time, and creates an ordered list from Tree Pin
TheArchitectmc25-Mar-10 2:39
memberTheArchitectmc25-Mar-10 2:39 
GeneralRe: Vote 4: Stanford has a better solution running on n(O) time, and creates an ordered list from Tree Pin
Mr.PoorEnglish28-Aug-10 12:13
memberMr.PoorEnglish28-Aug-10 12:13 
Generalum Pin
konikula6-Jan-10 22:31
memberkonikula6-Jan-10 22:31 
GeneralSomething similar Pin
leppie1-Apr-09 0:05
mvpleppie1-Apr-09 0:05 
GeneralVery nice! Pin
Huanacaraz28-Mar-09 9:19
memberHuanacaraz28-Mar-09 9:19 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.180111.1 | Last Updated 21 Feb 2008
Article Copyright 2008 by Mr.PoorEnglish
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid