If I was going to design a data structure to traverse, I would do things completely differently. However, I suspect that traversal isn't the only thing you're planning on doing.

In addition, you still haven't fully laid out the rules for the traversal. Here are the rules I've seen you lay out. You tell me if they make sense:

1. Take a key from the table you're in and append it to the list.
2. If there are no children, go to 1.
3. Grab the list of child records.
4. Append each child record to the list.
5. For each child record, go to 1.

------
/me wants to be the brightest bulb in the chandelier!

It's not as easy as saying "Can you traverse this or not?"

Of course it is! All of the relationships between the nodes are present and accounted for. Printing this out, I've explained this to two nonprogrammers; they recognize the pattern after a walkthrough, and given a much more complex example than the one I posted can easily traverse it. I've explained it to programmers and they can recognize the pattern and have so far failed to be able to write code to do it -- including me.

suspect that traversal isn't the only thing you're planning on doing

No, it's not. In fact, there's a whole ad-hoc report generation system which uses the "output" of this problem to produce reports. Sorts, breaks, totals, summary, detail, etc... The earlier incarnations of this routine suffered from bugs which caused either duplicate traversals or missed traversals in some very odd places.

In addition, you still haven't fully laid out the rules for the traversal.

That's because every time I try to quantify it, it breaks down at some level or another. Step 4.5 (which everyone seems to grasp intuitively, but not be able to describe) is "only after each child, once we've fully descended into the tree do we have a complete record; on the next child, the nodes descended by the first have to be thrown away and re-done". Sort of. But that's not clean enough to code and may not be entirely accurate.

I have much, much larger examples that aren't nearly so neat and tidy if necessary. They all follow this pattern though.

  A
 / \
B   C
   / \
  D   E
[download]

_____________________________________________________
Jeff japhy Pinyan: Perl, regex, and perl hacker.
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

Ummm...Yeah I think. Look at the data, it pretty-much speaks for itself but lemme try an english explanation. If this confuses someone, ignore it and go back to the data. :)

The simple setup

Let's simplify the explanation first. Let's say there's only a 1:1 relationship between records (for example). Starting with the first record, descend into each child table and pick up the record that's referred to by key.

So if your diagram above is the tables and how they relate to each other, we'd take the data from the record in A, the record from B, the record from C, the record from D and the record from E and accumulate those into a single output record.

On the next record in A, we'd traverse down into B, C, D, and E and grab the matching record from each of those and make another output record. And so on.

2 records in A would yeild 2 output records after joining together all of the child tables. This is because everything had a 1:1 relationship.

Now, it gets more complex

What if a table could have more than one matching record? (more than one child for a given parent) In my example, starting with "table a" and record "aa" if you follow the chain down you'll find that a parent in 'table c' can have a 1:n relationship with 'table d'.

So you traverse all of the tables as you did in the simple example, but having reached table D you take only one of the matching records. That makes an output record.

Do it again but take the other record from D, and that gives another output record. The 2:1 relationship between D and C gives you 2 records for each entry in A.

Now take the 'bb' start record from 'table a' above. Traversing it, you'll find a 2:1 relationship in both tables 'e' and 'd'. This means that for the start record 'bb' in 'table a' you wind up with 4 permutations on the output.

A simple recursion won't do, becuase you have to know when you've encountered a list to recurse into and at each node of the list stop and dump the results so-far. And the 1:n relationship between the records isn't known until you're at that node (no fair note-taking about the table's properties).