Finding All Unique Paths In A Tree Structure In Lucee CFML 5.3.7.47

<cfscript>

	// Setup our Tree for demonstration purposes. Each node in this tree is named based
	// on its depth and its order at a particular depth.
	tree = xmlParse("
		<a1>
			<b1>
				<c1>
					<d1 />
					<d2 />
					<d3 />
				</c1>
			</b1>
			<b2 />
			<b3>
				<c2 />
			</b3>
			<b4>
				<c3>
					<d4>
						<e1 />
						<e2>
							<f1>
								<g1>
									<h1>
										<i1>
											<j1 />
										</i1>
									</h1>
								</g1>
							</f1>
						</e2>
						<e3 />
					</d4>
					<d5 />
				</c3>
			</b4>
			<b5 />
		</a1>
	");

	printTreePaths( tree );

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

	/**
	* I perform a depth-first traversal of the given XML document, printing out the set
	* of unique paths to every leaf-node.
	* 
	* @tree I am the XML Document being walked.
	*/
	public void function printTreePaths( required xml tree ) {

		// The "recursive" nature of this tree traversal will be powered by this queue so
		// that we don't have to create a deep recursive call-stack. As each node is
		// visited, its child-nodes will be PREPENDED to the queue for further traversal.
		// Each node will be stored along with its depth so that we know how to "reset"
		// the path as we move from node to node.
		// --
		// ASIDE: "Prepending" nodes creates a depth-first traversal while "Appending"
		// nodes creates a breadth-first traversal.
		var queue = [{
			node: tree.xmlRoot,
			depth: 1
		}];
		var paths = [];
		var path = [];

		// Continue pulling nodes OFF THE FRONT of the queue until we have visited the
		// entire tree (depth-first).
		while ( queue.isDefined( 1 ) ) {

			var queueItem = arrayShift( queue );
			var node = queueItem.node;
			var depth = queueItem.depth;

			// As we move to each node, we may be moving BACK UP in the tree depth. The
			// size of this jump in depth will change based on the tree structure. As
			// such, we have to "trim" the current path back to what it was ABOVE THIS
			// NODE so that we then add this next as the LAST ITEM in the current path.
			arrayTrimTo( path, ( depth - 1 ) )
				.append( node )
			;

			// If there are any child nodes, queue them up for further exploration.
			if ( node.xmlChildren.len() ) {

				node.xmlChildren.each(
					( childNode, i ) => {

						// NOTE: All child-nodes are at the same depth in the tree.
						var newQueueItem = {
							node: childNode,
							depth: ( depth + 1 )
						};

						queue.insertAt( i, newQueueItem );

					}
				);

			// If this node has no children, it is a LEAF NODE; which means, it's the
			// terminal node in the current path. As such, we can store a copy of the
			// current path into the set of all collected paths.
			} else {

				paths.append( path.slice( 1 ) );

			}

		}

		// At this point, we've collected all of the paths in the tree structure. But,
		// that paths consist of complex XML data-structures. We need to map them onto
		// simple node-name representations.
		var delimiter = " <span style='color: deeppink ;'>&rarr;</span> "

		for ( var path in paths ) {

			var stringifiedPath = arrayPluck( path, "xmlName" )
				.toList( delimiter )
			;

			echo( stringifiedPath & "<br />" );

		}

	}

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

	// CAUTION: The following array functions may MUTATE the original array, which only
	// "works" as expected in Lucee CFML because arrays are PASSED BY REFERENCE. If your
	// runtime passes arrays by VALUE, none of this will work.

	public array function arrayPluck(
		required array values,
		required string propertyName
		) {

		var propertyValues = values.map(
			( value ) => {

				return( value[ propertyName ] );

			}
		);

		return( propertyValues );

	}


	/**
	* I remove the first value in the array and return it.
	* 
	* @values I am the array being mutated.
	*/
	public any function arrayShift( required array values ) {

		var firstValue = values.first();
		values.deleteAt( 1 );

		return( firstValue );

	}


	/**
	* I reduce the size of the array until it is less-than-or-equal-to the given length.
	* 
	* @values I am the array being mutated.
	* @length I am the length to which the array is being trimmed.
	*/
	public array function arrayTrimTo(
		required array values,
		required numeric length
		) {

		for ( var i = values.len() ; i > length ; i-- ) {

			values.deleteAt( i );

		}

		return( values );

	}

</cfscript>