JavaScript recursive function to put multimap data into a tree object-CodePudding

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

CodePudding user response：

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'))

CodePudding user response：

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();