[plt-scheme] Reverse Inside Out Tree Recursion

IIUC you want to generate a tree with pointers going from root to
leaves via a traversal from leaves to root. I think you can do this by
lazily generating the nodes as you need them. That is you have a
promise which promises to give you the parent of the children you pass
to it. Forcing the promise actually just creates the structure given
the arguments.

You might find useful material to do with zippers, which address a
related problem.

N.

On Mon, Mar 1, 2010 at 8:53 PM, Synx <plt at synx.us.to> wrote:
> 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.