Instantly share code, notes, and snippets.

Embed
What would you like to do?
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