Skip to content

Recursion with map function in javascript

I have a map like this, which represents a graph:

Map(5) {
  1 => [ 2, 3 ],
  2 => [ 7, 8, 10 ],
  3 => [ 4 ],
  10 => [ 12 ],
  4 => [ 11 ]
}

And I have this class, which creates a rooted tree:

class RootedTree {
    constructor (data, ...descendants) {
      this.data = data;
      this.descendants = descendants;
    }
}

My goal is: given a root, I want to convert that graph to a rooted tree. For the example above, using 1 as root, I want the following return:

const RT = (...args) => new RootedTree(...args) // just to simplify 
// goal return:
RT(1, RT(2, RT(7), RT(8), RT(10, RT(12))), RT(3, RT(4, RT(11)), RT(5))

Here’s my code:

let local_descendants = []
const toRT  = (root, node_map) => {
    rt = new RootedTree(root)
    if (node_map.get(root) !== undefined){
        node_map.get(root).map((node) => toRT(node, node_map), local_descendants)
    } else {
        return null
    }

    return local_descendants
}

rt = new RootedTree(1, toRT(1, map))

I’m receiving an empty array from the toRT function. I guess I probably messed up with the variables, but I don’t know how to fix it.

Answer

@Ajax’s answer is fine, but you mentioned that you had a Map, and wanted that Map instance to be an argument to toRT (good!).

So then the code is:

class RootedTree {
    constructor (data, ...descendants) {
        this.data = data;
        this.descendants = descendants;
    }
}

const toRT = (data, map) =>
    new RootedTree(data, ...map.get(data)?.map(child => toRT(child, map))??[]);

const map = new Map([[1,[2,3]],[2,[7,8,10]],[3,[4]],[10,[12]],[4,[11]]]);
const root = toRT(1, map);
console.log(root);

Explanation

From your question it is clear you are comfortable with Map and spread syntax, so let’s focus on this expression:

map.get(data)?.map(child => toRT(child, map))??[]

The optional chaining operator, i.e. ?., will ensure that .map() is only called when map.get(data) is defined. Otherwise undefined will be used instead of the .map() result.

.map() will iterate the child values found in the Map entry for data and translate each of them by a call to toRT(child, map). The latter will return a RootedTree instance, so the .map() call will return an array of such instances, and they will serve as descendants for the node we are constructing for data.

Finally, the Nullish coalescing operator, i.e. ??, will translate the undefined value (that came from map.get()) to an empty array. This way the spread operator will work correctly also in that case.

So the deeper nodes are created first, providing the descendants arguments for the outer new RootedTree calls. The root node is the last one created.