After our first attempt, we’re left with two things: an index of ItemIDs to Rows (RowFromID), and an array of the items that don’t have parents (within the chunk of the tree that we have) and are therefore logically root nodes (RootItems). Where do we go from here?
Let’s look at the Brute Force approach. We could loop through the query for each root node and build a Struct tree with the same structure as the result that we want. We could then look for the children of each node recursively by looping over the query to find them. Of course, we’d then have to write a recursive function to walk through our struct tree. Recursive functions are possible in ColdFusion, but they are also rather slow. Also, since we’re looping over the entire query for each item, we end up with quadratic slowdown as the query gets larger. A five-item query takes 25 loops, 10 takes 100, 20 takes 400, and so on. For those of you fresh out of CompSci who can still remember your Big O Notation, that’s O(n2). Since we started off with just a linear slowdown, O(n), that’s hopefully not the right track.
Since the ParentIDs don’t change we could optimize this approach by building another index, this time relating items to their children. In fact, we can just integrate this with the first loop in the code we already have. Since we know that parents will almost always have multiple children, we use an array to store them by simply appending the child’s ItemID. Throw that into a struct by ParentID and you’ve got another index:
<cfset RowFromID=StructNew()> <cfset ChildrenFromID=StructNew()> <cfloop query="Stuff"> <cfset RowFromID[ItemID]=CurrentRow> <cfif NOT StructKeyExists(ChildrenFromID, ParentID)> <cfset ChildrenFromID[ParentID]=ArrayNew(1)> </cfif> <cfset ArrayAppend(ChildrenFromID[ParentID], ItemID)> </cfloop>
Building this index allows us to eliminate that pesky inner loop that we were talking about and get us back to linear time instead of quadratic. Now we can just loop through our root items’ children, and their children recursively, and build our tree.
But there’s that word again: recursive. As a general rule, as a ColdFusion programmer, you’ll want to shy away from a solution that looks recursive. It can probably be done, and I’ve done my fair share of recursive CF, but odds are that there’s a better answer. Sometimes there aren’t better answers, but 99% of the time it’s worth the extra effort to try to find one.
In this situation, unraveling the recursion turns out to be surprisingly easy. That’s what we’ll look at next time.