Retrieving Hierarchically Recursive Data Iteratively

Many objects are recursive hierarchies (you can say, like the root system of a tree where roots have roots). The directories of a file system are recursive hierarchies since a directory can contain one or more subdirectories that can also contain one or more subdirectories. Windows of a GUI are recursive hierarchies since a window can contain client windows or controls (controls are windows) that can contain controls or other windows. Engineering and manufacturing parts lists (such as for refrigerators and spacecraft) are recursive hierarchies. Organizational structures (employees) are recursive hierarchies.

Recursively hierarchical data can be retrieved and processed recursively. For each parent item, such as a directory or a window, the function processing the structure can call itself for each child. It is very easy to design a way to retrieve hierarchical data recursively.

I have always wanted to process hierarchical data iteratively instead of recursively. Now that I have done it, I am surprised how easy it is. I won't explain the advantages and disadvantages of either. The purpose of this article is to explain how to iteratively process recursively hierarchical data and provide an example.

When processing data recursively, recursion uses a stack. Each time a function is called (recursively or not), the data for the calling function is pushed onto the stack. For a recursive call, part of that data is usually the parent item, such as the directory or window.

The trick to processing data iteratively (not recursively) is to simply use a ("to do") stack for the data that has not yet been processed but that needs to be processed. During the processing of a parent item, the children (that are then to be done) are stacked (using a Last-In-First-Out (LIFO) collection). The .Net Stack class can be used for that. Objects are pushed onto the stack and popped off the stack until all data is processed. The data is processed in reverse, in the sense that if "1", 2"", "3" and "4" are pushed onto the stack in that order then they are processed as "4", "3", "2" and "1".

See Processing Folders Iteratively for a sample of  processing folders iteratively.

Let us use the following data for the sample here.

• Top
• First
• First-1
• John
• Mike
• Steve
• First-2
• Susan
• Julie
• Kara
• First-3
• Kim
• Kelly
• Pat
• Second
• Second-1  
• Second-2  
• Second-3 

When processing the data iteratively, the stack would be as follows, one line per iteration:

Top
First Second
First-1 First-2 First-3 Second
John Mike Steve First-2 First-3 Second
Mike Steve First-2 First-3 Second
Steve First-2 First-3 Second
First-2 First-3 Second
Susan Julie Kara First-3 Second
Julie Kara First-3 Second
Kara First-3 Second
First-3 Second
Kim Kelly Pat Second
Kelly Pat Second
Pat Second
Second
Second-1 Second-2 Second-3
Second-2 Second-3
Second-3

In other words, we begin by pushing "Top" onto the stack. We then iterate (loop) by popping that off the stack and processing it. Processing includes pushing the children onto the stack. So the iteration continues until there are no more children to be processed; in other words, there is nothing more to process. Note that, as each item is processed, it is effectively replaced by its children, if any.

The sample program processes items of a class called "Hierarchy" that consists of:

class Hierarchy
{
    public string Name;
    public List<Hierarchy> Children = new List<Hierarchy>();

    public Hierarchy Parent = null;
        public Hierarchy(string Name, Hierarchy Parent)
    {
        this.Name = Name;
        this.Parent = Parent;
    }
}

The stack of items to be processed could then be: 

Stack<Hierarchy> ToDo = new Stack<Hierarchy>();

The data could be processed iteratively using: 

ToDo.Push(Top);
while (ToDo.Count > 0)
{
    Hierarchy h = ToDo.Pop();
    Put(h, ToDo);
}

Where the following is the "Put" method: 

private void Put(Hierarchy h, Stack<Hierarchy> ToDo)
{
    string tabs = new string('\t', Level);
    Console.WriteLine("{0}{1}", tabs, h.Name);
    // store the children in the to do stack
    if (h.Children == null)
        return;
    // since the stack is LIFO, the objects will be popped off in
    // reverse order from what they are pushed, so we will push
    // in reverse order
    for (int i = h.Children.Count - 1; i >= 0; --i)
        ToDo.Push(h.Children[i]);
}

See the sample code to see how "Level" is determined.

The following is an equivalent method for processing the data recursively:

private static void PutRecursively(Hierarchy h)
{
    string tabs = new string('\t', Level);
    Console.WriteLine("{0}{1}", tabs, h.Name);
    // store the children in the to do stack
    if (h.Children == null)
        return;
    foreach (Hierarchy child in h.Children)
        PutRecursively(child);
}