Stump the programmer

🧩 Stump the Programmer: The Recursive Shelf

The Problem

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

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

Sample data:

Included as JSON as well:

[
  { "id": 1, "parent_id": null, "name": "Fiction" },
  { "id": 2, "parent_id": 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" }
]

Write a single ColdFusion/BoxLang function that takes an array of structs (representing the flat table above) and returns a nested struct tree — without using any loops (no for, no while, no cfloop). Recursion only.

The output should be an ordered array of top-level category structs, each with a children key that itself contains an ordered array of child structs, and so on. Each node should look like:

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

Constraints:

• No loops of any kind — only recursion
• No external libraries
• Must work for arbitrarily deep nesting
• The function signature must be: function buildTree( array flatList, numeric parentId=0 ) — where parentId=0 represents the top level (treat NULL as 0)

💡 Hint

Think about what it means to "find all children of a given parent" using only recursion and array functions like arrayFilter(). Then think about how to attach children to each node — recursively.

✅ 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.

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