convert a flat json file to tree structure in javascript

Question

I am basically trying to convert a flat json file to tree view. Here the parent child relationship required for tree view is mentained by links key using source and target.

Here is the sample raw input:

{
  "nodes" : [
    {
      name: "bz_db",
      index: 0
    },
    {
      name: "mysql",
      index: 1
    },
    {
      name: "postgres",
      index: 2
    },
    {
      name: "it-infra",
      index: 3
    },
    {
      name: "user-count",
      index: 4
    }
  ],
  links: [
    {
      source: 0, target: 1
    },
    {
      source: 0, target: 3
    },
    {
      source: 1, target: 3
    },
    {
      source: 3, target: 4
    }
  ]
}

As you can see the link field maintains this relation ship, and finally I want my data in this format:

{
  name: "bz_db",
  children: [
    {
      name: "mysql",
      children: [
        {
          name: "it-infra",
          children: [
            {
              name: "user_count",
              children: []
            }
          ]
        }
      ]
    },
    {
      name: "it-infra",
      children: [{
          name: "user_count",
          children: []
        }
      ]
    }
  ]
}

I tried to solve this, but it worked for 1 level (to show immediate child of a selected root element.

var findObjectByKeyValue = function(arrayOfObject, key, value){
                    return _.find(arrayOfObject, function(o){ return o[key] == value})
                }

var rootObject = findObjectByKeyValue(sample_raw_input.nodes, 'name', 'bz_db');
var treeObject = {
                        name: rootObject.name,
                        index: rootObject.index,
                        root: true,
                        children: []
                    };
angular.forEach(dependencyData.links, function(eachLink){
                        if(treeObject.index == eachLink.source){
                            var rawChildObject = findObjectByKeyValue(dependencyData.nodes, 'index', eachLink.target);
                            var childObject = {};
                            childObject.index = rawChildObject.index;
                            childObject.name = rawChildObject.name;
                            childObject.children = [];
                            treeObject.children.push(childObject);
                        }
                    });

But the above code returns me only first level of depndencies, but i want hierarchical relationship. I know i can use recursion here. But I am not so comfortable with it.

Answer 1

Josh's answer uses a sequence of map->filter->map->find calls, each of which iterate thru a collection of data. This loop of loop of loop of loops results in a stunning amount of computational complexity as the number of nodes in your collection increases.

You can dramatically simplify the creation of the tree by using a single reduce pass on each nodes and links. Map can also perform look-ups in logarithmic time, compared to Array's find which requires linear time (slower). When you consider this operation is called for each element of the input, it's clear to see a significant difference in time.

const makeTree = (nodes = [], links = []) =>
  links.reduce
    ( (t, l) =>
        t.set ( l.source
              , MutableNode.push ( t.get (l.source)
                                 , t.get (l.target)
                                 )
              )
    , nodes.reduce
        ( (t, n) => t.set (n.index, MutableNode (n.name))
        , new Map
        )
    )
    .get (0)

Lastly, we provide the MutableNode interface we relied upon

const MutableNode = (name, children = []) =>
  ({ name, children })

MutableNode.push = (node, child) =>
  (node.children.push (child), node)

Below is a full program demonstration. JSON.stringify is used only to display the result

const MutableNode = (name, children = []) =>
  ({ name, children })
  
MutableNode.push = (node, child) =>
  (node.children.push (child), node)

const makeTree = (nodes = [], links = []) =>
  links.reduce
    ( (t, l) =>
        t.set ( l.source
              , MutableNode.push ( t.get (l.source)
                                 , t.get (l.target)
                                 )
              )
    , nodes.reduce
        ( (t, n) => t.set (n.index, MutableNode (n.name))
        , new Map
        )
    )
    .get (0)
    
const data =
  { nodes:
      [ { name: "bz_db", index: 0 }
      , { name: "mysql", index: 1 }
      , { name: "postgres", index: 2 }
      , { name: "it-infra", index: 3 }
      , { name: "user-count", index: 4 }
      ]
  , links: 
      [ { source: 0, target: 1 }
      , { source: 0, target: 3 }
      , { source: 1, target: 3 }
      , { source: 3, target: 4 }
      ]
  }

const tree = 
  makeTree (data.nodes, data.links)

console.log (JSON.stringify (tree, null, 2))

Answer 2

You can rely on tracking an object reference and do this without any recursion. Using Object.assign, map the list of nodes to its children:

// Assuming that input is in `input`
const nodes = input.nodes.reduce((a, node) => {
  a[node.index] = { ...node, index: undefined };
  return a;
}, []);

// organize the links by their source
const links = input.links.reduce((a, link) => {
  return a.set((a.get(link.source) || []).concat(nodes[link.target]);
}, new Map());

// Apply side effect of updating node children
nodes.forEach(node => Object.assign(node, {
  children: links.get(node.index),
}));

So I'm taking the list of nodes, and assigning to each (to mutate the node itself -- keep in mind this is a side-effect) a new array. Those children are all the links that link this node, and we Array#map them to convert their target ID into the actual node we want.