I am struggling to convert the JS recursive function below into a a trampoline function(s) in order to avoid maxing out the call stack with deep nodes.
It returns an array of all children nodes from the initial root node passed in. Note, list is a Map used to lookup the children of the current node for the next recursion iteration.
const getRootSet = (nodeId, list) => {
let results = [];
const node = list.get(nodeId);
if (node && node.children.size > 0) {
results.push(node.nodeId);
node.children.forEach((value, key) => {
results = results.concat(getRootSet(list.get(key).nodeId, list) );
});
}
if(node && node.children.size === 0)
{
//add last child node
results.push(node.nodeId);
}
return results;
}
How do I setup the trampoline structure in order to build the array of nodes to return at the end?
Sample data:
child, parent,
111111, 222222,
000000, 111111,
060270, 964240,
041342, 964240,
024367, 964240,
052643, 964240,
083020, 060270,
024367, 961758,
024367, 964264,
060270, 024367,
060270, 964240,
123456, 789100,
345678, 789100,
As we know that recursion uses memory stack to push and remember the next recursive function calls, so we need something to remember our next function calls. Here I'm using nodes
array to push child node ids for next execution cycle. On each node id first we check if it exists in the list
map. If yes then push it into results
and iterate its children and push child ids in nodes
for next cycle. Note that I'm checking if a child id has already been processed or not to avoid a cyclic infinite loop. And for the current node I'm using index
and the break point is the end of nodes
. Here's my solution:
const getRootSet = (rootNodeId, list) => {
let results = [];
let nodes = [rootNodeId];
let index = 0;
while(index < nodes.length) {
const node = list.get(nodes[index]);
if(node) {
results.push(node.nodeId);
if (node.children.size > 0) {
node.children.forEach((val, childId) => {
if(!nodes.includes(childId)) {
nodes.push(childId);
}
});
}
}
index++;
}
return results;
};
console.log(getRootSet('root', list));
Here's the sample code in js: https://ideone.com/Avnq9h