Stump the Programmer: The Recursive Shelf

I used to enjoy Raymond Camden's Friday Puzzler series, where he would pose programming questions for readers to solve. I decided to create my own puzzle series for the same reason—solving puzzles is fun. The first puzzle is inspired by a real problem I encountered while designing the comment system for DismalThreads, which needed to support unlimited nested child comments under parent comments.

---

The Problem

You're building a library cataloguing system. Books belong to categories, and categories can contain sub-categories (nested to any depth). Your database uses a single flat table:

CREATE TABLE categories (
    id        INT PRIMARY KEY,
    parent_id INT NULL,   -- NULL means top-level
    name      VARCHAR(100)
);

Sample Data

id	parent_id	name
1	NULL	Fiction
2	NULL	Non-Fiction
3	1	Science Fiction
4	1	Fantasy
5	3	Space Opera
6	3	Cyberpunk
7	4	Epic Fantasy
8	2	History
9	8	Ancient History
10	8	Modern History

Sample Data as ColdFusion Array

flatData = [
    { id: 1,  parent_id: javaCast("null",""), name: "Fiction" },
    { id: 2,  parent_id: javaCast("null",""), name: "Non-Fiction" },
    { id: 3,  parent_id: 1,  name: "Science Fiction" },
    { id: 4,  parent_id: 1,  name: "Fantasy" },
    { id: 5,  parent_id: 3,  name: "Space Opera" },
    { id: 6,  parent_id: 3,  name: "Cyberpunk" },
    { id: 7,  parent_id: 4,  name: "Epic Fantasy" },
    { id: 8,  parent_id: 2,  name: "History" },
    { id: 9,  parent_id: 8,  name: "Ancient History" },
    { id: 10, parent_id: 8,  name: "Modern History" }
];

Challenge

Write a single ColdFusion/BoxLang function that converts a flat array of category structs into a nested tree structure using recursion only—no loops.

Expected Output Structure

The function should return an ordered array of top-level category structs. Each struct includes a children key containing an ordered array of child structs, nested to any depth:

{
    id: 1,
    name: "Fiction",
    children: [
        {
            id: 3,
            name: "Science Fiction",
            children: [
                { id: 5, name: "Space Opera", children: [] },
                { id: 6, name: "Cyberpunk", children: [] }
            ]
        },
        ...
    ]
}

Function Signature and Constraints

function buildTree( array flatList, numeric parentId = 0 )

Requirements:

• Use recursion and functional array methods only—no loops of any kind
• No external libraries
• Support arbitrary nesting depth
• Treat NULL parent IDs as 0 (top-level categories)

Bonus challenge: Adapt the function to accept an optional sortKey argument that alphabetically sorts children by name at every level—still without any loops.

---

Solution

function buildTree( array flatList, numeric parentId=0 ) {

    var children = arrayFilter( flatList, function( item ) {
        var itemParent = isNull( item.parent_id ) ? 0 : item.parent_id;
        return itemParent == parentId;
    });

    return arrayMap( children, function( node ) {
        return {
            id:       node.id,
            name:     node.name,
            children: buildTree( flatList, node.id )
        };
    });
}

Usage:

flatData = [
    { id: 1,  parent_id: javaCast("null",""), name: "Fiction" },
    { id: 2,  parent_id: javaCast("null",""), name: "Non-Fiction" },
    { id: 3,  parent_id: 1,  name: "Science Fiction" },
    { id: 4,  parent_id: 1,  name: "Fantasy" },
    { id: 5,  parent_id: 3,  name: "Space Opera" },
    { id: 6,  parent_id: 3,  name: "Cyberpunk" },
    { id: 7,  parent_id: 4,  name: "Epic Fantasy" },
    { id: 8,  parent_id: 2,  name: "History" },
    { id: 9,  parent_id: 8,  name: "Ancient History" },
    { id: 10, parent_id: 8,  name: "Modern History" }
];

tree = buildTree( flatData );
writeDump( tree );

---

Why It Works

The key insight is that arrayFilter() and arrayMap() are higher-order functions—not loops. Each call to buildTree() filters the flat list for nodes matching the current parentId, then maps over them, recursively attaching their own subtrees. The recursion bottoms out naturally when a node has no children and arrayFilter() returns an empty array.

Complexity: O(n²)—for each node, the full flat list is scanned. For production use with large datasets, pre-indexing into a struct keyed by parent_id first would bring this down to O(n), but that requires a loop—defeating the constraint of this puzzle.