JavaScript recursive function to put multimap data into a tree object

Question

I have a general tree class with: myTree = new Tree(string), appendChildNode(node), createChildNode(string), myTree.print() functions and myTree.name, myTree.children, etc attributes.

I also have a multimap with data which I want to decompose and put into a tree object. Lets assume, the data has no circles in it. My idea is to let the recursion build the subbranches. For some reason the recursion does not work and I cannot figure out why. The return inside forEach gives me an 'undefined'

my multimap:

aaaa -> [b, c, d]
c    -> [f]
f    -> [g]
r    -> [p]

So my resulting tree for "aaaa" should be:

         aaaa
   b      c    d
        f
      g

my main function:

myMultiMap ... <multimap defined here>
myTree = new Tree('End2End')  // my tree object
// lets just pick the 'aaaa' to start with
myMultiMap.get('aaaa').forEach((entry) => {
  newNode = new Tree(entry)
  myTree.appendChildNode(recurse(newNode))

})
// show the tree after it was built
myTree.print()

recurse function

  function recurse (node) {
    // if the element is in the multimap, it has one or more children
    if(myMultiMap.has(node.name)) {
      // iterate through all children of the node in the multimap
      myMultiMap.get(node.name).forEach((child) => {
        // build a new node from the child
        newChildnode = new Tree(child);
        // build a subtree recursively, since this child could have children itself
        return node.appendChildNode(recurse(newChildnode))
      })
    
    // if the node is not in the multimap, thus it has no children, so just return the node   
    } else {
        return node
    }
  }

Info: I took this tree implementation: https://github.com/beforesemicolon/tutorials-files/blob/master/tree-generic.js

Answer 1

Using a trivial tree implementation and using a Map of strings to arrays of strings in place of your MultiMap implementation, we can see the structure fairly clearly:

const tree = (name, children) => ({name, children})

const mapToTree = (multiMap) => (root) => 
  tree (root, (multiMap .get (root) || []) .map (mapToTree (multiMap)))

const myMultiMap = new Map ([
  ['aaaa', ['b', 'c', 'd']],
  ['c', ['f']],
  ['f', ['g']],
  ['r', ['p']]
])

console .log (mapToTree (myMultiMap) ('aaaa'))

.as-console-wrapper {max-height: 100% !important; top: 0}

If you want an external wrapper node, End2End, we can just wrap one more call to tree:

const myTree = tree ('End2End', mapToTree (myMultiMap) ('aaaa'))

Update

From a comment:

your answer is brilliant, thanks.

I'm afraid it's anything but brilliant. I wrote this with the intent of coming back and extending it in several directions, and adding much more explanation. Somehow, as I shut down my machine, though, I just saw a working answer with a brief explanation and posted it regardless. Here I'll try to rectify that.

It is a bit too advanced though imho to be easily understood for a beginner (like me) without further code comments.

It is not actually very advanced, and uses techniques which if you don't know already are easy enough to understand. Let me start with a version which might seem more familiar.

First, the tree building function is really as simple as it gets. A tree is simply an object with name and children properties. We construct one by passing a name and a list of children to the function tree. (Ideally, this should have been called node, but often enough they are used interchangeably.) The tree we build has no features to add or remove children or to change the name. While nothing prevents you from mutating the value, it's not encouraged. Immutable data is often much easier to reason about.

We could have written this in this format:

const tree = (nodeName, nodeChildren) => {
  return {
    name: nodeName, 
    children: nodeChildren
  }
}

but when an arrow function contains nothing but a return statement, we can use the basic syntax, removing the curly braces and return statement, to yield

const tree = (nodeName, nodeChildren) => ({
  name: nodeName, 
  children: nodeChildren
})

(Note that when the return is an Object literal, for technical reasons, you must wrap it in parentheses.)

Now, when an object property has the same name as an in-scope variable, there is an object initializer shorthand that lets you just use that name, so if we change the parameter names to match our name and children properties, we can simplify this to just

const tree = (name, children) => ({name, children})

Let's do the same with the main function. Here is another version of mapToTree:

const mapToTree = (multiMap, root) => {
  const childNames = multiMap .get (root) || []
  const children = childNames .map (name => mapToTree (multiMap, name))
  return tree (root, children)
}

There are only two real differences between this one any the one I first presented. First, since the local variables childNames and children are each only used once, I inlined them to turn this into something like:

const mapToTree = (multiMap, root) => {
  return tree (root, (multiMap .get (root) || []) .map (name => mapToTree (multiMap, name)))
}

then turned this into a simpler arrow function as above by removing the curly braces and return keyword, leaving:

const mapToTree = (multiMap, root) => 
  tree (root, (multiMap .get (root) || []) .map (name => mapToTree (multiMap, name)))

Second, I curried this function so that instead of (multiMap, root) => ... it is (multiMap) => (root) => .... There are many benefits to currying, and I tend to do this to most functions, but here it offers the simplification that mapToTree (myMultiMap) is a function that now takes a key value and returns a tree. So it's suitable for passing to map over an array of child names, and we can replace name => mapToTree (multiMap, name) with just mapToTree (multiMap), which gives us back the initial version:

const mapToTree = (multiMap) => (root) => 
  tree (root, (multiMap .get (root) || []) .map (mapToTree (multiMap)))

In truth, I did not go through these steps. I've been doing this a while, and I wrote these pretty much in the format you see them in, but I hope it makes them a little more clear.

I am also not sure if your solution would be easy to extend. For instance if I would want additionally every node to have its own "depth": "5" key, and a key for the amount of all children "siblings": "12" below it.

I'm not quite sure what you would be looking for here, but if you want the nodes to track their depth in the tree and to have a property listing the number of descendants, then we could alter it like this:

const tree = (name, children, depth, descendentCount) => 
  ({name, depth, descendentCount, children})

const mapToTree = (multiMap, root, depth = 0) => {
  const childNames = multiMap .get (root) || []
  const children = childNames .map (name => mapToTree (multiMap, name, depth + 1))
  const descendentCount = children .reduce (
    (count, child) => count + child.descendentCount + 1,
    0
  )
  return tree (root, children, depth, descendentCount)
}

const myMultiMap = new Map ([
  ['aaaa', ['b', 'c', 'd']],
  ['c', ['f']],
  ['f', ['g']],
  ['r', ['p']]
])

console .log (mapToTree (myMultiMap, 'aaaa'))

.as-console-wrapper {max-height: 100% !important; top: 0}

---

None of this deals with your tree implementation or your MultiMap. It looks as though this simple Map is a good enough replacement for your purposes. But this tree is significantly simpler than the one you link to. I'm hoping this is enough to let you extend in that direction as needed, but if not, Bergi's answer shows what you did wrong, and how to fix it.

The point here is simply to show how simple the recursion might be.

Answer 2

The return inside forEach gives me an 'undefined'

Yes, you cannot return out of a forEach callback. But that's not what you want to do anyway. Instead, after performing the loop, you want return node:

function recurse(node) {
  if (myMultiMap.has(node.name)) {
    myMultiMap.get(node.name).forEach((child) => {
      const newChildnode = new Tree(child);
      node.appendChildNode(recurse(newChildnode))
    })
    return node;
  } else {
    return node;
  }
}

or simply

function recurse(node) {
  if (myMultiMap.has(node.name)) {
    myMultiMap.get(node.name).forEach((child) => {
      const newChildnode = new Tree(child);
      node.appendChildNode(recurse(newChildnode))
    })
  }
  return node;
}

Alternatively, don't return the node at all, just write

function recurse(node) {
  if (myMultiMap.has(node.name)) {
    myMultiMap.get(node.name).forEach((child) => {
      const newChildnode = new Tree(child);
      recurse(newChildnode);
      node.appendChildNode(newChildnode);
    })
  }
}

or maybe nicer, instead move the node creation inside the recurse function:

function recurse(name) {
  const node = new Tree(name);
  if (myMultiMap.has(name)) {
    myMultiMap.get(name).forEach((child) => {
      node.appendChildNode(recurse(child))
    })
  }
  return node;
}

Btw, in your main code you don't need to duplicate the loop. Simplify it to

const myMultiMap = …; // multimap defined here
const myTree = recurse(new Tree('aaaa'));
myTree.print();

or for my last version, respectively

const myMultiMap = …; // multimap defined here
const myTree = recurse('aaaa');
myTree.print();