[plt-scheme] Reverse Inside Out Tree Recursion

I've been trying to figure out the algorithm for a very weird form of
tree recursion. It's one that starts with generating the leaves and adds
parents as necessary to make sure there is one single root. The amount
of leaves isn't knowable as they might be streamed, but the amount of
children per node is known and constant. Every node has only one parent,
so after that parent relationship has been determined, the node can be
serialized to disk and garbage collected, meaning only "unfinished
nodes" have to be in active memory at any given time.

I made a script demonstrating how this would work. Unfortunately since I
only know the algorithm heuristically I had to manually specify how to
generate the tree. You can visually see what I'm talking about though.
Green nodes are still active, red nodes are safely written to disk and
forgotten. Each node has at most 4 children, but until the very end all
nodes have exactly the maximum 4 children. (4 is arbitrary, but any more
would have required way too much typing!)

I know how to accomplish this task upside down, where I start with the
parent, and recurse down until I've gotten to the bottom level. But I'm
not generating the tree in a way that I know how many levels it has at
the beginning. I'm just loading in the leaf nodes, and propogating up
parent nodes as necessary.

I want an algorithmic way to handle the generation of data structures
like this. Obviously making a list of all the nodes in order with my
typey fingers isn't the most ideal of algorithms. Something that
continues adding leaf nodes at the bottom (top?) level, but also adds
parent nodes where needed so that when it's finished I have one single
root that I can return as representative of the entire tree.

In a real world application some trees may be many gigabytes large, so
I'd like to make sure not to require having the entire tree in memory at
any given point.
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: generate.ss
URL: <http://lists.racket-lang.org/users/archive/attachments/20100301/c5689534/attachment.ksh>