Skip to content

Instantly share code, notes, and snippets.

@mveteanu
Last active February 22, 2022 00:57
Show Gist options
  • Save mveteanu/1f1d49bc6b764bfb1b1000a92bd3b48a to your computer and use it in GitHub Desktop.
Save mveteanu/1f1d49bc6b764bfb1b1000a92bd3b48a to your computer and use it in GitHub Desktop.
Process hierarchical data using recursion or stack

Process hierarchical data using recursion or stack

This is an example of how to process data in hierarchical structures using either recursion or a stack based approach. To examplify this we will use a didactical example: find the maximum number in an array of arrays. The same techniques can be used to find / process data in other hierarchical structure such as XML documents, JSON objects, etc.

<script>
var ar = [2, 4, 10, [12, 4, [100, 99], 4], [3, 2, 99], 0];
console.log( findMax1(ar) );
console.log( findMax2(ar) );
// Use recursion to find the maximum numeric value in an array of arrays
function findMax1(ar)
{
var max = -Infinity;
// Cycle through all the elements of the array
for(var i = 0; i < ar.length; i++)
{
var el = ar[i];
// If an element is of type array then invoke the same function
// to find out the maximum element of that subarray
if ( Array.isArray(el) )
{
el = findMax1( el );
}
if ( el > max )
{
max = el;
}
}
return max;
}
// Use a stack to find the maximum numeric value in an array of arrays
function findMax2(arElements)
{
var max = -Infinity;
// This is the stack on which will put the first array and then
// all the other sub-arrays that we find as we traverse an array
var arrays = [];
arrays.push(arElements);
// Loop as long as are arrays added to the stack for processing
while(arrays.length > 0)
{
// Extract an array from the stack
ar = arrays.pop();
// ... and loop through its elements
for(var i = 0; i < ar.length; i++)
{
var el = ar[i];
// If an element is of type array, we'll add it to stack
// to be processed later
if ( Array.isArray(el) )
{
arrays.push(el);
continue;
}
if ( el > max )
{
max = el;
}
}
}
return max;
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment