Building Tree Structures From Hierarchical Data In ColdFusion

[
	{ "id": 1,  "parentID": 0, "name": "Fiction" },
	{ "id": 2,  "parentID": 0, "name": "Non-Fiction" },
	{ "id": 3,  "parentID": 1, "name": "Science Fiction" },
	{ "id": 4,  "parentID": 1, "name": "Fantasy" },
	{ "id": 5,  "parentID": 3, "name": "Space Opera" },
	{ "id": 6,  "parentID": 3, "name": "Cyberpunk" },
	{ "id": 7,  "parentID": 4, "name": "Epic Fantasy" },
	{ "id": 8,  "parentID": 2, "name": "History" },
	{ "id": 9,  "parentID": 8, "name": "Ancient History" },
	{ "id": 10, "parentID": 8, "name": "Modern History" }
]

<cfscript>

	// Data and exploratory concept borrowed from:
	// https://kisdigital.com/posts/2026/04/stump-the-programmer-the-recursive-shelf
	flatData = [
		[ id: 1,  parentID: 0, name: "Fiction" ],
		[ id: 2,  parentID: 0, name: "Non-Fiction" ],
		[ id: 3,  parentID: 1, name: "Science Fiction" ],
		[ id: 4,  parentID: 1, name: "Fantasy" ],
		[ id: 5,  parentID: 3, name: "Space Opera" ],
		[ id: 6,  parentID: 3, name: "Cyberpunk" ],
		[ id: 7,  parentID: 4, name: "Epic Fantasy" ],
		[ id: 8,  parentID: 2, name: "History" ],
		[ id: 9,  parentID: 8, name: "Ancient History" ],
		[ id: 10, parentID: 8, name: "Modern History" ],
	];

	// Version 1: using the data as-is, in the order it was provided.
	writeDump(
		var = buildTree( flatData ),
		label = "Unsorted"
	);

	// Version 2: sorting the data first. Since the array is grouped as-is, and then woven
	// together as-is, if we sort the original array, the sort will be maintained through
	// the entire algorithm.
	// --
	// Note: the buildTree() algorithm is idempotent in that it will just overwrite the
	// already-injected "children" array from the first version.
	writeDump(
		var = buildTree( arraySortOn( flatData, "name" ) ),
		label = "Sorted"
	);

	// ------------------------------------------------------------------------------- //
	// ------------------------------------------------------------------------------- //

	/**
	* I build a hierarchical tree from the given array-of-structs. A "children" array is
	* injected IN PLACE within each struct based on the "parentID" relationship. Elements
	* that have no children receive an empty array.
	*/
	private array function buildTree( required array data ) {

		// The algorithm does two passes on the array - O(n). The first pass creates an
		// index that groups every element by the "parentID". The second pass uses said
		// index to weave the elements together.
		var indexByParent = arrayGroupBy( data, "parentID" );

		// Pass 2: weave the elements together via the index.
		for ( var element in data ) {

			element.children = ( indexByParent[ element.id ] ?: [] );

		}

		// The root of the tree is the layer of elements that has no parent.
		return indexByParent[ 0 ];

	}


	/**
	* I return an index of the given array with elements grouped by the given keyed-value.
	*/
	private struct function arrayGroupBy(
		required array input,
		required string key
		) {

		var index = {};

		for ( var element in input ) {

			var facet = toString( element[ key ] );

			if ( index.keyExists( facet ) ) {

				index[ facet ].append( element );

			} else {

				index[ facet ] = [ element ];

			}

		}

		return index;

	}


	/**
	* I sort the given array on the value sorted in the given key.
	*/
	private array function arraySortOn(
		required array input,
		required string key
		) {

		return input.sort( ( a, b ) => compareNoCase( a[ key ], b[ key ] ) );

	}

</cfscript>