Recursion - Converting Javascript Map into a nested JSON object

Question

Thank you in advance for the help!

I'm attempting to convert a specific javascript map into a nested JSON object. A sample of the map looks like:

["a", ["b", "c"]]
["b", ["e"]]
["c", ["f"]]
["e", []]
["f", []]

where the key represents a parent node, and the values in the arrays are its direct children. Empty arrays for values indicates no children for that given key. I would like to generate an output that looks like:

{
    "name": “a”,
    "children": [{
        "name": “b”,
        "children": [{
            "name": “e”
            }]
        }, {
            "name": “c”,
            "children": [{
                "name": “f”,
            }]
        }]
}

(this may not be a well-formed json object as typed, but hopefully is illustrative of the hierarchical relationship the javascript example map is demonstrating). Additionally, though trivial, the keys nor the values in the arrays are assumed to be sorted.

Lastly, I know this lends itself to a recursive solution. Any help would be immensely appreciated. Thank you again for the time!

Mauricio Poppe · Accepted Answer · 2015-03-17 06:01:28Z

The algorithm you want to learn to solve this problem is called topological sorting, it assumes that the graph you have described above doesn't have a cycle, but for the case above the algorithm can be modified a little bit to find only the nodes which have no parent to be the root nodes.

A possible solution:

var hasParent = {};

function computeParentCount(data) {
  stack = [];
  for (key in data) {
    data[key].forEach(function (child) {
      hasParent[child] = true;
    });
  }
}

function appendAfterDfs(res, data, key) {
  var node = {
    name: key
  };
  if (data[key].length) {
    // only nodes with a children array with more than 0 elements
    // have children in the json
    node.children = [];
  }
  data[key].forEach(function (child) {
    appendAfterDfs(node.children, data, child);
  });
  res.push(node);
}

function main() {

  var data = {
    'a': ['b', 'c'],
    'b': ['e'],
    'c': ['f'],
    'e': [],
    'f': [],
  };

  computeParentCount(data);

  // build the json
  var res = [];
  for (key in data) {
    if (!hasParent[key]) {
      appendAfterDfs(res, data, key);
    }
  }
  document.write('<pre>' + JSON.stringify(res, null, '  ') + '</pre>');
}

main()

Explanation:

First find the keys which have no parent (and call them the root nodes)
with each root node perform a dfs through the data object until a node doesn't have any children
collect each node in the process (saving it in the parent's children array)

JLRishe · Accepted Answer · 2015-03-17 06:37:29Z

If we can assume that the first item in your list is the "top" item and that there are no loops or anything like that, then there is a fairly simple solution:

function buildTree(items) {
  // build map of node name -> node
  var map = items.reduce(function(l, n) {
    l[n[0]] = { name: n[0] };
    return l;
  }, {});

  // assign children
  items.filter(function(it) { return it[1].length; })
  .forEach(function(it) {
    map[it[0]].children = it[1].map(function(key) {
      return map[key];
    });
  });

  // return the node for the first item in `items`
  return map[items[0][0]];
}

var tree = buildTree([
  ["a", ["b", "c"]],
  ["b", ["e"]],
  ["c", ["f"]],
  ["e", []],
  ["f", []]
]);

console.log(tree);

Collectives™ on Stack Overflow

Recursion - Converting Javascript Map into a nested JSON object

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related