For my PerlMonks::NewestNodes module, I used a technique very similar to the one described by mikfire. All the nodes are stored in a hash indexed by node ID, and each element is a hash reference containing the different pieces of information about the node.

The thread subroutine receives as argument a list of nodes to thread (this allows adding new nodes to the existing structure without rethreading everything). Then it goes through those nodes, and for each one it visits its parent and inserts its ID into the parent's "kids" element, which is an array ordered chronologically. Nodes that do not have a parent_node element are marked as "top nodes".

This is complicated a little bit by the fact that the Newest Nodes XML Generator will give you a node, but not its parent, when the parent is already marked as seen. So the thread subroutine also checks to see which nodes it doesn't have yet, and adds those to a list of "nodes to get". The nodes without parents are added to a list of "nodes to rethread". Nodes that are threaded correctly are removed from the list. At the end, any necessary nodes are grabbed (using the Node Query XML Generator, you pass it an argument of the form "nodes=id1,id2,..."), added to the list, and the loop repeats.

Once every node has its kids element properly populated, it's just a matter of descending recursively from each "top node" to generate its tree of replies.

Shameless plug: check out Shendal's Perl/Tk Newest Nodes Client, which uses my module to show you a very nice threaded display of the Newest Nodes.

--ZZamboni