Retrieving Hierarchically Recursive Data Iteratively

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.

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.