226

I have a complex json file that I have to handle with javascript to make it hierarchical, in order to later build a tree. Every entry of the json has : id : a unique id, parentId : the id of the parent node (which is 0 if the node is a root of the tree) level : the level of depth in the tree

The json data is already "ordered". I mean that an entry will have above itself a parent node or brother node, and under itself a child node or a brother node.

Input :

{
    "People": [
        {
            "id": "12",
            "parentId": "0",
            "text": "Man",
            "level": "1",
            "children": null
        },
        {
            "id": "6",
            "parentId": "12",
            "text": "Boy",
            "level": "2",
            "children": null
        },
                {
            "id": "7",
            "parentId": "12",
            "text": "Other",
            "level": "2",
            "children": null
        },
        {
            "id": "9",
            "parentId": "0",
            "text": "Woman",
            "level": "1",
            "children": null
        },
        {
            "id": "11",
            "parentId": "9",
            "text": "Girl",
            "level": "2",
            "children": null
        }
    ],
    "Animals": [
        {
            "id": "5",
            "parentId": "0",
            "text": "Dog",
            "level": "1",
            "children": null
        },
        {
            "id": "8",
            "parentId": "5",
            "text": "Puppy",
            "level": "2",
            "children": null
        },
        {
            "id": "10",
            "parentId": "13",
            "text": "Cat",
            "level": "1",
            "children": null
        },
        {
            "id": "14",
            "parentId": "13",
            "text": "Kitten",
            "level": "2",
            "children": null
        },
    ]
}

Expected output :

{
    "People": [
        {
            "id": "12",
            "parentId": "0",
            "text": "Man",
            "level": "1",
            "children": [
                {
                    "id": "6",
                    "parentId": "12",
                    "text": "Boy",
                    "level": "2",
                    "children": null
                },
                {
                    "id": "7",
                    "parentId": "12",
                    "text": "Other",
                    "level": "2",
                    "children": null
                }   
            ]
        },
        {
            "id": "9",
            "parentId": "0",
            "text": "Woman",
            "level": "1",
            "children":
            {

                "id": "11",
                "parentId": "9",
                "text": "Girl",
                "level": "2",
                "children": null
            }
        }

    ],    

    "Animals": [
        {
            "id": "5",
            "parentId": "0",
            "text": "Dog",
            "level": "1",
            "children": 
                {
                    "id": "8",
                    "parentId": "5",
                    "text": "Puppy",
                    "level": "2",
                    "children": null
                }
        },
        {
            "id": "10",
            "parentId": "13",
            "text": "Cat",
            "level": "1",
            "children": 
            {
                "id": "14",
                "parentId": "13",
                "text": "Kitten",
                "level": "2",
                "children": null
            }
        }

    ]
}
3
  • 2
    There are several ways to do that, did you try anything yet?
    – bfavaretto
    Commented Aug 2, 2013 at 13:23
  • I assume that a parentId of 0 means there is no parent id and should be the top layer. Commented Apr 12, 2016 at 11:28
  • 2
    Usually these kind of tasks required extensive working knowledge objects. Good question Commented Oct 14, 2018 at 11:14

34 Answers 34

250

There is an efficient solution if you use a map-lookup. If the parents always come before their children you can merge the two for-loops. It supports multiple roots. It gives an error on dangling branches, but can be modified to ignore them. It doesn't require a 3rd-party library. It's, as far as I can tell, the fastest solution.

function list_to_tree(list) {
  var map = {}, node, roots = [], i;
  
  for (i = 0; i < list.length; i += 1) {
    map[list[i].id] = i; // initialize the map
    list[i].children = []; // initialize the children
  }
  
  for (i = 0; i < list.length; i += 1) {
    node = list[i];
    if (node.parentId !== "0") {
      // if you have dangling branches check that map[node.parentId] exists
      list[map[node.parentId]].children.push(node);
    } else {
      roots.push(node);
    }
  }
  return roots;
}

var entries = [{
    "id": "12",
    "parentId": "0",
    "text": "Man",
    "level": "1",
    "children": null
  },
  {
    "id": "6",
    "parentId": "12",
    "text": "Boy",
    "level": "2",
    "children": null
  },
  {
    "id": "7",
    "parentId": "12",
    "text": "Other",
    "level": "2",
    "children": null
  },
  {
    "id": "9",
    "parentId": "0",
    "text": "Woman",
    "level": "1",
    "children": null
  },
  {
    "id": "11",
    "parentId": "9",
    "text": "Girl",
    "level": "2",
    "children": null
  }
];

console.log(list_to_tree(entries));

If you're into complexity theory this solution is Θ(n log(n)). The recursive-filter solution is Θ(n^2) which can be a problem for large data sets.

17
  • 43
    keep in mind that with this solution, your nodes must be ordered specifically to make sure the parents are pushed into the map first, otherwise the lookup process will error... so you either need to sort em on the level property, or you need to push them into the map first. and use a separate for loop for the lookup. (i prefer sort however when you don't have a level property the separate loops might be an option)
    – Sander
    Commented Nov 15, 2013 at 18:55
  • I found it surprising at first that having additional information, eg: a path like [1, 5, 6] where the array is the subsequent ancestors, couldn't be used efficiently in it. But looking at the code it kinda makes sens since I believe it is O(n)
    – Ced
    Commented Apr 3, 2017 at 10:44
  • 1
    Despite of the good answer, it is complex. Apply my answer for just two line codes: link Commented Aug 26, 2017 at 10:25
  • Please can you explain why this solution is Θ(n log(n)), It seems to be taking O(n) time. Commented Mar 7, 2018 at 7:34
  • 4
    @Halcyon lookup in maps takes constant time i.e O(1). Commented Mar 8, 2018 at 18:17
139

( BONUS1 : NODES MAY or MAY NOT BE ORDERED )

( BONUS2 : NO 3RD PARTY LIBRARY NEEDED, PLAIN JS )

( BONUS3 : User "Elias Rabl" says this is the most performant solution, see his answer below )

Here it is:

const createDataTree = dataset => {
  const hashTable = Object.create(null);
  dataset.forEach(aData => hashTable[aData.ID] = {...aData, childNodes: []});
  const dataTree = [];
  dataset.forEach(aData => {
    if(aData.parentID) hashTable[aData.parentID].childNodes.push(hashTable[aData.ID])
    else dataTree.push(hashTable[aData.ID])
  });
  return dataTree;
};

Here is a test, it might help you to understand how the solution works :

it('creates a correct shape of dataTree', () => {
  const dataSet = [{
    "ID": 1,
    "Phone": "(403) 125-2552",
    "City": "Coevorden",
    "Name": "Grady"
  }, {
    "ID": 2,
    "parentID": 1,
    "Phone": "(979) 486-1932",
    "City": "Chełm",
    "Name": "Scarlet"
  }];

  const expectedDataTree = [{
    "ID": 1,
    "Phone": "(403) 125-2552",
    "City": "Coevorden",
    "Name": "Grady",
    childNodes: [{
      "ID": 2,
      "parentID": 1,
      "Phone": "(979) 486-1932",
      "City": "Chełm",
      "Name": "Scarlet",
      childNodes : []
    }]
  }];

  expect(createDataTree(dataSet)).toEqual(expectedDataTree);
});
7
  • 3
    Wouldn't it be more accurate if we added childNodes only when needed? By removing them from the first forEach and moving them inside the second?
    – arpl
    Commented Oct 15, 2019 at 15:15
  • @FurkanO really nice solution, however would it be possible to get anywhere near this performance with functional programming (no mutations)
    – Dac0d3r
    Commented Apr 29, 2020 at 20:54
  • In case anyone want to have multiple parent for a child, refer -> stackoverflow.com/a/65626153/8577819
    – natrayan
    Commented Jan 8, 2021 at 15:05
  • Can I get childrens of specific item?
    – rendom
    Commented Nov 20, 2021 at 5:53
  • For those looking for a generic way implemented in TypeScript: gist.github.com/ggondim/35376795cb832103e466fc158db74af4 Commented Jan 18, 2022 at 0:03
81

As mentioned by @Sander, @Halcyon`s answer assumes a pre-sorted array, the following does not. (It does however assume you have loaded underscore.js - though it could be written in vanilla javascript):

Code

// Example usage
var arr = [
    {'id':1 ,'parentid' : 0},
    {'id':2 ,'parentid' : 1},
    {'id':3 ,'parentid' : 1},
    {'id':4 ,'parentid' : 2},
    {'id':5 ,'parentid' : 0},
    {'id':6 ,'parentid' : 0},
    {'id':7 ,'parentid' : 4}
];

unflatten = function( array, parent, tree ){
    tree = typeof tree !== 'undefined' ? tree : [];
    parent = typeof parent !== 'undefined' ? parent : { id: 0 };
        
    var children = _.filter( array, function(child){ return child.parentid == parent.id; });
    
    if( !_.isEmpty( children )  ){
        if( parent.id == 0 ){
           tree = children;   
        }else{
           parent['children'] = children
        }
        _.each( children, function( child ){ unflatten( array, child ) } );                    
    }
    
    return tree;
}

tree = unflatten( arr );
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))
<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore-min.js"></script>

Requirements

It assumes the properties 'id' and 'parentid' indicate ID and parent ID respectively. There must be elements with parent ID 0, otherwise you get an empty array back. Orphaned elements and their descendants are 'lost'

http://jsfiddle.net/LkkwH/1/

10
  • 5
    You can add else { parent['children'] = []; } after the first if-clause to ensure that every node has an attribute children (it'll be empty if the node is a leaf node) Commented Apr 12, 2016 at 10:20
  • 2
    Your code snippet worked perfectly, thank you!! The only thing is: tree is never passed as an argument when calling the function recursively, so i think the line tree = typeof tree !== 'undefined' ? tree : []; can be replaced by let tree = []; Commented Jan 12, 2017 at 13:19
  • could this be modified to allow null parent_ids instead of 0? Edit: Nevermind, I got it working by changing the id: 0 to id: null.
    – dlinx90
    Commented Jan 23, 2017 at 8:34
  • 2
    Keep in mind that the above answer uses two loops, and hence could be improved. Since I could not find a npm module which implements a O(n) solution, I created the following one (unit tested, 100% code coverage, only 0.5 kb in size and includes typings). Maybe it helps someone: npmjs.com/package/performant-array-to-tree Commented May 7, 2017 at 17:42
  • 5
    For anyone interested, the code is easily converted to vanilla js: jsfiddle.net/LkkwH/853
    – xec
    Commented Apr 12, 2018 at 9:58
71

Use this ES6 approach. Works like charm

// Data Set
// One top level comment 
const comments = [{
    id: 1,
    parent_id: null
}, {
    id: 2,
    parent_id: 1
}, {
    id: 3,
    parent_id: 1
}, {
    id: 4,
    parent_id: 2
}, {
    id: 5,
    parent_id: 4
}];

const nest = (items, id = null, link = 'parent_id') =>
  items
    .filter(item => item[link] === id)
    .map(item => ({ ...item, children: nest(items, item.id) }));

console.log(
  nest(comments)
)

4
  • 7
    The shortest and best answer I think
    – bekliev
    Commented Nov 29, 2019 at 7:38
  • 6
    sloooow compared to FurkanO's answer
    – Geza Turi
    Commented Dec 17, 2019 at 17:44
  • 2
    don't work if array have more then one null parentId Commented May 9, 2021 at 13:32
  • yes, is there a way to make it work with multiple null parentids?
    – chovy
    Commented Nov 15, 2022 at 18:20
38

Had the same problem, but I could not be certain that the data was sorted or not. I could not use a 3rd party library so this is just vanilla Js; Input data can be taken from @Stephen's example;

 var arr = [
        {'id':1 ,'parentid' : 0},
        {'id':4 ,'parentid' : 2},
        {'id':3 ,'parentid' : 1},
        {'id':5 ,'parentid' : 0},
        {'id':6 ,'parentid' : 0},
        {'id':2 ,'parentid' : 1},
        {'id':7 ,'parentid' : 4},
        {'id':8 ,'parentid' : 1}
      ];
    function unflatten(arr) {
      var tree = [],
          mappedArr = {},
          arrElem,
          mappedElem;

      // First map the nodes of the array to an object -> create a hash table.
      for(var i = 0, len = arr.length; i < len; i++) {
        arrElem = arr[i];
        mappedArr[arrElem.id] = arrElem;
        mappedArr[arrElem.id]['children'] = [];
      }


      for (var id in mappedArr) {
        if (mappedArr.hasOwnProperty(id)) {
          mappedElem = mappedArr[id];
          // If the element is not at the root level, add it to its parent array of children.
          if (mappedElem.parentid) {
            mappedArr[mappedElem['parentid']]['children'].push(mappedElem);
          }
          // If the element is at the root level, add it to first level elements array.
          else {
            tree.push(mappedElem);
          }
        }
      }
      return tree;
    }

var tree = unflatten(arr);
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))

JS Fiddle

Flat Array to Tree

2
  • in some cases mappedArr[mappedElem['parentid']]['children'] was failing as can't access to children of undefined. Commented Sep 6, 2018 at 13:36
  • how would I start at parent id:1 ?
    – vinni
    Commented Oct 18, 2018 at 12:54
18

a more simple function list-to-tree-lite

npm install list-to-tree-lite

listToTree(list)

source:

function listToTree(data, options) {
    options = options || {};
    var ID_KEY = options.idKey || 'id';
    var PARENT_KEY = options.parentKey || 'parent';
    var CHILDREN_KEY = options.childrenKey || 'children';

    var tree = [],
        childrenOf = {};
    var item, id, parentId;

    for (var i = 0, length = data.length; i < length; i++) {
        item = data[i];
        id = item[ID_KEY];
        parentId = item[PARENT_KEY] || 0;
        // every item may have children
        childrenOf[id] = childrenOf[id] || [];
        // init its children
        item[CHILDREN_KEY] = childrenOf[id];
        if (parentId != 0) {
            // init its parent's children object
            childrenOf[parentId] = childrenOf[parentId] || [];
            // push it into its parent's children object
            childrenOf[parentId].push(item);
        } else {
            tree.push(item);
        }
    };

    return tree;
}

jsfiddle

0
18

You can handle this question with just two line coding:

flatArray.forEach(f=>
       {f.nodes=flatArray.filter(g=>g.parentId===f.id)});
var resultArray=flatArray.filter(f=>f.parentId==null);

var flatArray =
    [{
        id: 1, parentId: null, text: "parent1"
    }
        , {
        id: 2, parentId: null, text: "parent2"
    }
        ,
    {
        id: 3, parentId: 1, text: "childId3Parent1"
    }
        ,
    {
        id: 4, parentId: 1, text: "childId4Parent1"
    }
        ,
    {
        id: 5, parentId: 2, text: "childId5Parent2"
    }
        ,
    {
        id: 6, parentId: 2, text: "childId6Parent2"
    }
        ,
    {
        id: 7, parentId: 3, text: "childId7Parent3"
    }
        ,
    {
        id: 8, parentId: 5, text: "childId8Parent5"
    }];
    flatArray.forEach(f=>
           {f.nodes=flatArray.filter(g=>g.parentId===f.id)});

        var resultArray=flatArray.filter(f=>f.parentId==null);
    console.log(resultArray)

No need to lodash library now: @Abed abuSalah

Good luck

3
  • This solution is O(n^2)
    – cbr
    Commented Jun 15, 2022 at 20:13
  • Is that good or bad?
    – chovy
    Commented Nov 16, 2022 at 0:34
  • Your solution works without lodash Commented Nov 22, 2022 at 22:05
7

It may be useful package list-to-tree Install:

bower install list-to-tree --save

or

npm install list-to-tree --save

For example, have list:

var list = [
  {
    id: 1,
    parent: 0
  }, {
    id: 2,
    parent: 1
  }, {
    id: 3,
    parent: 1
  }, {
    id: 4,
    parent: 2
  }, {
    id: 5,
    parent: 2
  }, {
    id: 6,
    parent: 0
  }, {
    id: 7,
    parent: 0
  }, {
    id: 8,
    parent: 7
  }, {
    id: 9,
    parent: 8
  }, {
    id: 10,
    parent: 0
  }
];

Use package list-to-tree:

var ltt = new LTT(list, {
  key_id: 'id',
  key_parent: 'parent'
});
var tree = ltt.GetTree();

Result:

[{
  "id": 1,
  "parent": 0,
  "child": [
    {
      "id": 2,
      "parent": 1,
      "child": [
        {
          "id": 4,
          "parent": 2
        }, {
          "id": 5, "parent": 2
        }
      ]
    },
    {
      "id": 3,
      "parent": 1
    }
  ]
}, {
  "id": 6,
  "parent": 0
}, {
  "id": 7,
  "parent": 0,
  "child": [
    {
      "id": 8,
      "parent": 7,
      "child": [
        {
          "id": 9,
          "parent": 8
        }
      ]
    }
  ]
}, {
  "id": 10,
  "parent": 0
}];
6
  • 2
    Note that link-only answers are discouraged, SO answers should be the end-point of a search for a solution (vs. yet another stopover of references, which tend to get stale over time). Please consider adding a stand-alone synopsis here, keeping the link as a reference
    – kleopatra
    Commented Sep 1, 2015 at 8:06
  • I don't understand why the -1,I think that it's a good solution but unfortunately I don't find the package in gitHub or in another public repository
    – oriaj
    Commented Oct 16, 2015 at 21:01
  • Thank you for your attention to the package. I plan to later expand it. Here is a link to the repository github.com/DenQ/list-to-tree
    – DenQ
    Commented Oct 17, 2015 at 8:13
  • @oriaj I am glad that the project benefit. The plans of a few ideas
    – DenQ
    Commented Oct 19, 2015 at 17:25
  • Works nicely, thank you @DenQ. Wish it had more test coverage though!
    – IliasT
    Commented Oct 23, 2015 at 5:13
7

I've written a test script to evaluate the performance of the two most general solutions (meaning that the input does not have to be sorted beforehand and that the code does not depend on third party libraries), proposed by users shekhardtu (see answer) and FurkanO (see answer).

http://playcode.io/316025?tabs=console&script.js&output

FurkanO's solution seems to be the fastest.

/*
** performance test for https://stackoverflow.com/questions/18017869/build-tree-array-from-flat-array-in-javascript
*/

// Data Set (e.g. nested comments)
var comments = [{
    id: 1,
    parent_id: null
}, {
    id: 2,
    parent_id: 1
}, {
    id: 3,
    parent_id: 4
}, {
    id: 4,
    parent_id: null
}, {
    id: 5,
    parent_id: 4
}];

// add some random entries
let maxParentId = 10000;
for (let i=6; i<=maxParentId; i++)
{
  let randVal = Math.floor((Math.random() * maxParentId) + 1);
  comments.push({
    id: i,
    parent_id: (randVal % 200 === 0 ? null : randVal)
  });
}

// solution from user "shekhardtu" (https://stackoverflow.com/a/55241491/5135171)
const nest = (items, id = null, link = 'parent_id') =>
  items
    .filter(item => item[link] === id)
    .map(item => ({ ...item, children: nest(items, item.id) }));
;

// solution from user "FurkanO" (https://stackoverflow.com/a/40732240/5135171)
const createDataTree = dataset => {
    let hashTable = Object.create(null)
    dataset.forEach( aData => hashTable[aData.id] = { ...aData, children : [] } )
    let dataTree = []
    dataset.forEach( aData => {
      if( aData.parent_id ) hashTable[aData.parent_id].children.push(hashTable[aData.id])
      else dataTree.push(hashTable[aData.id])
    } )
    return dataTree
};


/*
** lets evaluate the timing for both methods
*/
let t0 = performance.now();
let createDataTreeResult = createDataTree(comments);
let t1 = performance.now();
console.log("Call to createDataTree took " + Math.floor(t1 - t0) + " milliseconds.");

t0 = performance.now();
let nestResult = nest(comments);
t1 = performance.now();
console.log("Call to nest took " + Math.floor(t1 - t0) + " milliseconds.");




//console.log(nestResult);
//console.log(createDataTreeResult);

// bad, but simple way of comparing object equality
console.log(JSON.stringify(nestResult)===JSON.stringify(createDataTreeResult));

2
  • playcode.io gives an error "error: Uncaught ReferenceError: global is not defined"; however pasting into browser code works just fine; for everyone wondering - createDataTree is about 15-16 faster than the other one
    – ddruganov
    Commented Oct 17, 2021 at 12:22
  • Yes, this should be accepted answer, although I don't understand how it works without recursion.
    – chovy
    Commented Nov 16, 2022 at 0:39
7

After many tries I came up with this:

const arrayToTree = (arr, parent = 0) => arr .filter(item => item.parent === parent).map(child => ({ ...child, children: arrayToTree(arr, child.index) }));

   

const entries = [
  {
    index: 1,
    parent: 0
  },
  {
    index: 2,
    parent: 1
  },
  {
    index: 3,
    parent: 2
  },
  {
    index: 4,
    parent: 2
  },
  {
    index: 5,
    parent: 4
  },
  {
    index: 6,
    parent: 5
  },
  {
    index: 7,
    parent: 6
  },
  {
    index: 8,
    parent: 7
  },
  {
    index: 9,
    parent: 8
  },
  {
    index: 10,
    parent: 9
  },
  {
    index: 11,
    parent: 7
  },
  {
    index: 13,
    parent: 11
  },
  {
    index: 12,
    parent: 0
  }
];

const arrayToTree = (arr, parent = 0) => arr .filter(item => item.parent === parent) .map(child => ({ ...child, children: arrayToTree(arr, child.index) })); console.log(arrayToTree(entries));

2
  • 2
    (item.parent ?? 0) add this one for case parent empty.
    – dungtv
    Commented Nov 23, 2022 at 16:44
  • @dungtv Usually the parent will be there cause we are getting the data from the backend. And I tried to see if the code fails when there's no parent or when it's empty and it still holds. could it be that I didn't fully understand you? Commented May 19, 2023 at 9:38
5

UPDATE 2022

This is a proposal for unordered items. This function works with a single loop and with a hash table and collects all items with their id. If a root node is found, then the object is added to the result array.

const
    getTree = (data, root) => {
        const t = {};
        data.forEach(o => ((t[o.parentId] ??= {}).children ??= []).push(Object.assign(t[o.id] ??= {}, o)));
        return t[root].children;
    },
    data = { People: [{ id: "12", parentId: "0", text: "Man", level: "1", children: null }, { id: "6", parentId: "12", text: "Boy", level: "2", children: null }, { id: "7", parentId: "12", text: "Other", level: "2", children: null }, { id: "9", parentId: "0", text: "Woman", level: "1", children: null }, { id: "11", parentId: "9", text: "Girl", level: "2", children: null }], Animals: [{ id: "5", parentId: "0", text: "Dog", level: "1", children: null }, { id: "8", parentId: "5", text: "Puppy", level: "2", children: null }, { id: "10", parentId: "13", text: "Cat", level: "1", children: null }, { id: "14", parentId: "13", text: "Kitten", level: "2", children: null }] },
    result = Object.fromEntries(Object
        .entries(data)
        .map(([k, v]) => [k, getTree(v, '0')])
    );

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

3

Convert nodes Array to Tree

ES6 function to convert an Array of nodes (related by parent ID) - to a Tree structure:

/**
 * Convert nodes list related by parent ID - to tree.
 * @syntax getTree(nodesArray [, rootID [, propertyName]])
 *
 * @param {Array} arr   Array of nodes
 * @param {integer} id  Defaults to 0
 * @param {string} p    Property name. Defaults to "parent_id"
 * @returns {Object}    Nodes tree
 */

const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => {

  if (!o[n.id]) o[n.id] = {};
  if (!o[n[p]]) o[n[p]] = {};
  if (!o[n[p]].nodes) o[n[p]].nodes= [];
  if (o[n.id].nodes) n.nodes= o[n.id].nodes;

  o[n[p]].nodes.push(n);
  o[n.id] = n;

  return o;
}, {});

Generate HTML List from nodes Tree

Having our Tree in place, here's a recursive function to build the UL > LI Elements:

/**
 * Convert Tree structure to UL>LI and append to Element
 * @syntax getTree(treeArray [, TargetElement [, onLICreatedCallback ]])
 *
 * @param {Array} tree Tree array of nodes
 * @param {Element} el HTMLElement to insert into
 * @param {function} cb Callback function called on every LI creation
 */

const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => {
  const li = document.createElement('li');

  if (cb) cb.call(li, n);
  if (n.nodes?.length) treeToHTML(n.nodes, li, cb);

  ul.append(li);
  return ul;
}, document.createElement('ul')));

Demo time

Here's an example having a linear Array of nodes and using both the above functions:

const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => {
  if (!o[n.id]) o[n.id] = {};
  if (!o[n[p]]) o[n[p]] = {};
  if (!o[n[p]].nodes) o[n[p]].nodes = [];
  if (o[n.id].nodes) n.nodes = o[n.id].nodes;
  o[n[p]].nodes.push(n);
  o[n.id] = n;
  return o;
}, {});


const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => {
  const li = document.createElement('li');
  if (cb) cb.call(li, n);
  if (n.nodes?.length) treeToHTML(n.nodes, li, cb);
  ul.append(li);
  return ul;
}, document.createElement('ul')));


// DEMO TIME:

const nodesList = [
  {id: 10,  parent_id: 4,  text: "Item 10"}, // PS: Order does not matters
  {id: 1,   parent_id: 0,  text: "Item 1"},  
  {id: 4,   parent_id: 0,  text: "Item 4"},
  {id: 3,   parent_id: 5,  text: "Item 3"},
  {id: 5,   parent_id: 4,  text: "Item 5"},
  {id: 2,   parent_id: 1,  text: "Item 2"},
];
const myTree = getTree(nodesList)[0].nodes; // Get nodes of Root (0)

treeToHTML(myTree, document.querySelector("#tree"), function(node) {
  this.textContent = `(${node.parent_id} ${node.id}) ${node.text}`;
  this._node = node;
  this.addEventListener('click', clickHandler);
});

function clickHandler(ev) {
  if (ev.target !== this) return;
  console.clear();
  console.log(this._node.id);
};
<div id="tree"></div>

3

Array elements can be in a chaotic order

let array = [
  { id: 1, data: 'something', parent_id: null, children: [] },
  { id: 2, data: 'something', parent_id: 1, children: [] },
  { id: 5, data: 'something', parent_id: 4, children: [] },
  { id: 4, data: 'something', parent_id: 3, children: [] },
  { id: 3, data: 'something', parent_id: null, children: [] },
  { id: 6, data: 'something', parent_id: null, children: [] }
]

function buildTree(array) {
  let tree = []
  for (let i = 0; i < array.length; i++) {
    if (array[i].parent_id) {
      let parent = array.filter(elem => elem.id === array[i].parent_id).pop()
      parent.children.push(array[i])
    } else {
      tree.push(array[i])
    }
  }
  return tree
}

const tree = buildTree(array)
console.log(tree);
.as-console-wrapper { min-height: 100% }

2

I like @WilliamLeung's pure JavaScript solution, but sometimes you need to make changes in existing array to keep a reference to object.

function listToTree(data, options) {
  options = options || {};
  var ID_KEY = options.idKey || 'id';
  var PARENT_KEY = options.parentKey || 'parent';
  var CHILDREN_KEY = options.childrenKey || 'children';

  var item, id, parentId;
  var map = {};
    for(var i = 0; i < data.length; i++ ) { // make cache
    if(data[i][ID_KEY]){
      map[data[i][ID_KEY]] = data[i];
      data[i][CHILDREN_KEY] = [];
    }
  }
  for (var i = 0; i < data.length; i++) {
    if(data[i][PARENT_KEY]) { // is a child
      if(map[data[i][PARENT_KEY]]) // for dirty data
      {
        map[data[i][PARENT_KEY]][CHILDREN_KEY].push(data[i]); // add child to parent
        data.splice( i, 1 ); // remove from root
        i--; // iterator correction
      } else {
        data[i][PARENT_KEY] = 0; // clean dirty data
      }
    }
  };
  return data;
}

Exapmle: https://jsfiddle.net/kqw1qsf0/17/

0
2

I used @FurkanO answer and made a generic function that can be used with any object type, I also wrote this function in TypeScript which i love it more because of auto completions.

Implementation:

1. Javascript:

export const flatListToTree = (flatList, idPath, parentIdPath, childListPath, isParent) => {
  const rootParents = [];
  const map = {};
  for (const item of flatList) {
    if (!item[childListPath]) item[childListPath] = [];
    map[item[idPath]] = item;
  }
  for (const item of flatList) {
    const parentId = item[parentIdPath];
    if (isParent(item)) {
      rootParents.push(item);
    } else {
      const parentItem = map[parentId];
      parentItem[childListPath].push(item);
    }
  }
  return rootParents;
};

2. TypeScript: I've assumed the "T" type has a property for children List, you can change 'childListPath' to be a string instead of "keyof T" if you have different use case.

export const flatListToTree = <T>(
  flatList: T[],
  idPath: keyof T,
  parentIdPath: keyof T,
  childListPath: keyof T,
  isParent: (t: T) => boolean,
) => {
  const rootParents: T[] = [];
  const map: any = {};
  for (const item of flatList) {
    if (!(item as any)[childListPath]) (item as any)[childListPath] = [];
    map[item[idPath]] = item;
  }
  for (const item of flatList) {
    const parentId = item[parentIdPath];
    if (isParent(item)) {
      rootParents.push(item);
    } else {
      const parentItem = map[parentId];
      parentItem[childListPath].push(item);
    }
  }
  return rootParents;
};

How to use:

  const nodes = [
    { id: 2, pid: undefined, children: [] },
    { id: 3, pid: 2 },
    { id: 4, pid: 2 },
    { id: 5, pid: 4 },
    { id: 6, pid: 5 },
    { id: 7, pid: undefined },
    { id: 8, pid: 7 },
  ];
  
  const result = flatListToTree(nodes, "id", "pid", "children", node => node.pid === undefined);
1

var data = [{"country":"india","gender":"male","type":"lower","class":"X"},
			{"country":"china","gender":"female","type":"upper"},
			{"country":"india","gender":"female","type":"lower"},
			{"country":"india","gender":"female","type":"upper"}];
var seq = ["country","type","gender","class"];
var treeData = createHieArr(data,seq);
console.log(treeData)
function createHieArr(data,seq){
	var hieObj = createHieobj(data,seq,0),
		hieArr = convertToHieArr(hieObj,"Top Level");
		return [{"name": "Top Level", "parent": "null",
				     "children" : hieArr}]
	function convertToHieArr(eachObj,parent){
		var arr = [];
		for(var i in eachObj){
			arr.push({"name":i,"parent":parent,"children":convertToHieArr(eachObj[i],i)})
		}
		return arr;
	}
	function createHieobj(data,seq,ind){
		var s = seq[ind];
		if(s == undefined){
			return [];
		}
		var childObj = {};
		for(var ele of data){
			if(ele[s] != undefined){
				if(childObj[ele[s]] == undefined){
					childObj[ele[s]] = [];
				}
				childObj[ele[s]].push(ele);
			}
		}
		ind = ind+1;
		for(var ch in childObj){
			childObj[ch] = createHieobj(childObj[ch],seq,ind)
		}
		return childObj;
	}
}

2
  • I created this function to convert data from array of objects to tree structure,which is required for d3 tree interactive chart. With Only 40 lines of code I was able to get the output. I wrote this function in an efficent way usign recursive funtionality in js. Try and let me know your feedback. Thank you!!!! Commented Oct 31, 2017 at 19:18
  • Thanks for the anwser..It works perfectly for my d3 tree topology.. Now i have requirement that i need to change the node color based on the values of the node..So for that i need to pass a flag value in the JSON. How do i do that.. { "name": "Top Level", "flag" : 1, "parent": "null", "children": [ { "name": "india", "flag" : 0, "parent": "Top Level", "children": [ Commented Jul 30, 2018 at 7:04
1

this is what i used in a react project

// ListToTree.js
import _filter from 'lodash/filter';
import _map from 'lodash/map';

export default (arr, parentIdKey) => _map(_filter(arr, ar => !ar[parentIdKey]), ar => ({
  ...ar,
  children: _filter(arr, { [parentIdKey]: ar.id }),
}));

usage:

// somewhere.js
import ListToTree from '../Transforms/ListToTree';

const arr = [
   {
      "id":"Bci6XhCLZKPXZMUztm1R",
      "name":"Sith"
   },
   {
      "id":"C3D71CMmASiR6FfDPlEy",
      "name":"Luke",
      "parentCategoryId":"ltatOlEkHdVPf49ACCMc"
   },
   {
      "id":"aS8Ag1BQqxkO6iWBFnsf",
      "name":"Obi Wan",
      "parentCategoryId":"ltatOlEkHdVPf49ACCMc"
   },
   {
      "id":"ltatOlEkHdVPf49ACCMc",
      "name":"Jedi"
   },
   {
      "id":"pw3CNdNhnbuxhPar6nOP",
      "name":"Palpatine",
      "parentCategoryId":"Bci6XhCLZKPXZMUztm1R"
   }
];
const response = ListToTree(arr, 'parentCategoryId');

output:

[
   {
      "id":"Bci6XhCLZKPXZMUztm1R",
      "name":"Sith",
      "children":[
         {
            "id":"pw3CNdNhnbuxhPar6nOP",
            "name":"Palpatine",
            "parentCategoryId":"Bci6XhCLZKPXZMUztm1R"
         }
      ]
   },
   {
      "id":"ltatOlEkHdVPf49ACCMc",
      "name":"Jedi",
      "children":[
         {
            "id":"C3D71CMmASiR6FfDPlEy",
            "name":"Luke",
            "parentCategoryId":"ltatOlEkHdVPf49ACCMc"
         },
         {
            "id":"aS8Ag1BQqxkO6iWBFnsf",
            "name":"Obi Wan",
            "parentCategoryId":"ltatOlEkHdVPf49ACCMc"
         }
      ]
   }
]```
1

I had similar issue couple days ago when have to display folder tree from flat array. I didn't see any solution in TypeScript here so I hope it will be helpful.

In my cases main parent were only one, also rawData array don't have to be sorted. Solutions base on prepare temp object like {parentId: [child1, child2, ...] }

example raw data

const flatData: any[] = Folder.ofCollection([
  {id: '1', title: 'some title' },
  {id: '2', title: 'some title', parentId: 1 },
  {id: '3', title: 'some title', parentId: 7 },
  {id: '4', title: 'some title', parentId: 1 },
  {id: '5', title: 'some title', parentId: 2 },
  {id: '6', title: 'some title', parentId: 5 },
  {id: '7', title: 'some title', parentId: 5 },

]);

def of Folder

export default class Folder {
    public static of(data: any): Folder {
        return new Folder(data);
    }

    public static ofCollection(objects: any[] = []): Folder[] {
        return objects.map((obj) => new Folder(obj));
    }

    public id: string;
    public parentId: string | null;
    public title: string;
    public children: Folder[];

    constructor(data: any = {}) {
        this.id = data.id;
        this.parentId = data.parentId || null;
        this.title = data.title;
        this.children = data.children || [];
    }
}

SOLUTION: Function that returns tree structure for flat argument

    public getTree(flatData: any[]): Folder[] {
        const addChildren = (item: Folder) => {
            item.children = tempChild[item.id] || [];
            if (item.children.length) {
                item.children.forEach((child: Folder) => {
                    addChildren(child);
                });
            }
        };

        const tempChild: any = {};
        flatData.forEach((item: Folder) => {
            const parentId = item.parentId || 0;
            Array.isArray(tempChild[parentId]) ? tempChild[parentId].push(item) : (tempChild[parentId] = [item]);
        });

        const tree: Folder[] = tempChild[0];
        tree.forEach((base: Folder) => {
            addChildren(base);
        });
        return tree;
    }
1

I wrote an ES6 version based on @Halcyon answer

const array = [
  {
    id: '12',
    parentId: '0',
    text: 'one-1'
  },
  {
    id: '6',
    parentId: '12',
    text: 'one-1-6'
  },
  {
    id: '7',
    parentId: '12',
    text: 'one-1-7'
  },

  {
    id: '9',
    parentId: '0',
    text: 'one-2'
  },
  {
    id: '11',
    parentId: '9',
    text: 'one-2-11'
  }
];

// Prevent changes to the original data
const arrayCopy = array.map(item => ({ ...item }));

const listToTree = list => {
  const map = {};
  const roots = [];

  list.forEach((v, i) => {
    map[v.id] = i;
    list[i].children = [];
  });

  list.forEach(v => (v.parentId !== '0' ? list[map[v.parentId]].children.push(v) : roots.push(v)));

  return roots;
};

console.log(listToTree(arrayCopy));

The principle of this algorithm is to use "map" to establish an index relationship. It is easy to find "item" in the list by "parentId", and add "children" to each "item", because "list" is a reference relationship, so "roots" will Build relationships with the entire tree.

1

Based on @FurkanO's answer, I created another version that does not mutate the origial data (like @Dac0d3r requested). I really liked @shekhardtu's answer, but realized it had to filter through the data many times. I thought a solution could be to use FurkanO's answer by copying the data first. I tried my version in jsperf, and the results where unfortunately (very) bleak... It seems like the accepted answer is really a good one! My version is quite configurable and failsafe though, so I share it with you guys anyway; here is my contribution:

function unflat(data, options = {}) {
    const { id, parentId, childrenKey } = {
        id: "id",
        parentId: "parentId",
        childrenKey: "children",
        ...options
    };
    const copiesById = data.reduce(
        (copies, datum) => ((copies[datum[id]] = datum) && copies),
        {}
    );
    return Object.values(copiesById).reduce(
        (root, datum) => {
            if ( datum[parentId] && copiesById[datum[parentId]] ) {
                copiesById[datum[parentId]][childrenKey] = [ ...copiesById[datum[parentId]][childrenKey], datum ];
            } else {
                root = [ ...root, datum ];
            }
            return root
        }, []
    );
}

const data = [
    {
        "account": "10",
        "name": "Konto 10",
        "parentAccount": null
    },{
        "account": "1010",
        "name": "Konto 1010",
        "parentAccount": "10"
    },{
        "account": "10101",
        "name": "Konto 10101",
        "parentAccount": "1010"
    },{
        "account": "10102",
        "name": "Konto 10102",
        "parentAccount": "1010"
    },{
        "account": "10103",
        "name": "Konto 10103",
        "parentAccount": "1010"
    },{
        "account": "20",
        "name": "Konto 20",
        "parentAccount": null
    },{
        "account": "2020",
        "name": "Konto 2020",
        "parentAccount": "20"
    },{
        "account": "20201",
        "name": "Konto 20201",
        "parentAccount": "2020"
    },{
        "account": "20202",
        "name": "Konto 20202",
        "parentAccount": "2020"
    }
];

const options = {
    id: "account",
    parentId: "parentAccount",
    childrenKey: "children"
};

console.log(
    "Hierarchical tree",
    unflat(data, options)
);

With the options parameter, it is possible to configure what property to use as id or parent id. It is also possible to configure the name of the children property, if someone wants "childNodes": [] or something.

OP could simply use default options:

input.People = unflat(input.People);

If the parent id is falsy (null, undefined or other falsy values) or the parent object does not exist, we consider the object to be a root node.

1

My solution:

  • Allows bi-directional mapping (root to leaves and leaves to root)
  • Returns all nodes, roots, and leaves
  • One data pass and very fast performance
  • Vanilla Javascript
/**
 * 
 * @param data items array
 * @param idKey item's id key (e.g., item.id)
 * @param parentIdKey item's key that points to parent (e.g., item.parentId)
 * @param noParentValue item's parent value when root (e.g., item.parentId === noParentValue => item is root)
 * @param bidirectional should parent reference be added
 */
function flatToTree(data, idKey, parentIdKey, noParentValue = null, bidirectional = true) {
  const nodes = {}, roots = {}, leaves = {};

  // iterate over all data items
  for (const i of data) {

    // add item as a node and possibly as a leaf
    if (nodes[i[idKey]]) { // already seen this item when child was found first
      // add all of the item's data and found children
      nodes[i[idKey]] = Object.assign(nodes[i[idKey]], i);
    } else { // never seen this item
      // add to the nodes map
      nodes[i[idKey]] = Object.assign({ $children: []}, i);
      // assume it's a leaf for now
      leaves[i[idKey]] = nodes[i[idKey]];
    }

    // put the item as a child in parent item and possibly as a root
    if (i[parentIdKey] !== noParentValue) { // item has a parent
      if (nodes[i[parentIdKey]]) { // parent already exist as a node
        // add as a child
        (nodes[i[parentIdKey]].$children || []).push( nodes[i[idKey]] );
      } else { // parent wasn't seen yet
        // add a "dummy" parent to the nodes map and put the item as its child
        nodes[i[parentIdKey]] = { $children: [ nodes[i[idKey]] ] };
      }
      if (bidirectional) {
        // link to the parent
        nodes[i[idKey]].$parent = nodes[i[parentIdKey]];
      }
      // item is definitely not a leaf
      delete leaves[i[parentIdKey]];
    } else { // this is a root item
      roots[i[idKey]] = nodes[i[idKey]];
    }
  }
  return {roots, nodes, leaves};
}

Usage example:

const data = [{id: 2, parentId: 0}, {id: 1, parentId: 2} /*, ... */];
const { nodes, roots, leaves } = flatToTree(data, 'id', 'parentId', 0);
1
  • 1
    I voted for this reply more than because it was a solution, because of its excellent wording. Incredibly well documented! Congratulations! This is how all codes should be written. Commented Jan 4, 2023 at 11:28
1

ES6 Map version :

getTreeData = (items) => {
  if (items && items.length > 0) {
    const data = [];
    const map = {};
    items.map((item) => {
      const id = item.id; // custom id selector !!!
      if (!map.hasOwnProperty(id)) {
        // in case of duplicates
        map[id] = {
          ...item,
          children: [],
        };
      }
    });
    for (const id in map) {
      if (map.hasOwnProperty(id)) {
        let mappedElem = [];
        mappedElem = map[id];
        /// parentId : use custom id selector for parent
        if (
          mappedElem.parentId &&
          typeof map[mappedElem.parentId] !== "undefined"
        ) {
          map[mappedElem.parentId].children.push(mappedElem);
        } else {
          data.push(mappedElem);
        }
      }
    }
    return data;
  }
  return [];
};

/// use like this :

const treeData = getTreeData(flatList);
1

Incase anyone needs it for multiple parent. Refer id 2 which has multiple parents

  const dataSet = [{
        "ID": 1,    
        "Phone": "(403) 125-2552",
        "City": "Coevorden",
        "Name": "Grady"
      }, 
        {"ID": 2,
        "Phone": "(403) 125-2552",
        "City": "Coevorden",
        "Name": "Grady"
      },
      {
        "ID": 3,
        "parentID": [1,2],
        "Phone": "(979) 486-1932",
        "City": "Chełm",
        "Name": "Scarlet"
      }];




      const expectedDataTree = [
       {
          "ID":1,
          "Phone":"(403) 125-2552",
          "City":"Coevorden",
          "Name":"Grady",
          "childNodes":[{
                "ID":2,
                "parentID":[1,3],
                "Phone":"(979) 486-1932",
                "City":"Chełm",
                "Name":"Scarlet",
                "childNodes":[]
             }]
       },
       {
          "ID":3,
          "parentID":[],
          "Phone":"(403) 125-2552",
          "City":"Coevorden",
          "Name":"Grady",
          "childNodes":[
             {
                "ID":2,
                "parentID":[1,3],
                "Phone":"(979) 486-1932",
                "City":"Chełm",
                "Name":"Scarlet",
                "childNodes":[]
             }
          ]
       }
    ];
      
      
      const createDataTree = dataset => {
      const hashTable = Object.create(null);
      dataset.forEach(aData => hashTable[aData.ID] = {...aData, childNodes: []});
      const dataTree = [];
      dataset.forEach(Datae => {  
        if (Datae.parentID  && Datae.parentID.length > 0) {    
          Datae.parentID.forEach( aData => {    
            hashTable[aData].childNodes.push(hashTable[Datae.ID])
        });
        }
        else{
        dataTree.push(hashTable[Datae.ID])
        }
        
      });
      return dataTree;
    };   
    
    window.alert(JSON.stringify(createDataTree(dataSet)));

0

Here's a simple helper function that I created modeled after the above answers, tailored to a Babel environment:

import { isEmpty } from 'lodash'

export default function unflattenEntities(entities, parent = {id: null}, tree = []) {

  let children = entities.filter( entity => entity.parent_id == parent.id)

  if (!isEmpty( children )) {
    if ( parent.id == null ) {
      tree = children
    } else {
      parent['children'] = children
    }
    children.map( child => unflattenEntities( entities, child ) )
  }

  return tree

}
0
0

also do it with lodashjs(v4.x)

function buildTree(arr){
  var a=_.keyBy(arr, 'id')
  return _
   .chain(arr)
   .groupBy('parentId')
   .forEach(function(v,k){ 
     k!='0' && (a[k].children=(a[k].children||[]).concat(v));
   })
   .result('0')
   .value();
}
0

Here is a modified version of Steven Harris' that is plain ES5 and returns an object keyed on the id rather than returning an array of nodes at both the top level and for the children.

unflattenToObject = function(array, parent) {
  var tree = {};
  parent = typeof parent !== 'undefined' ? parent : {id: 0};

  var childrenArray = array.filter(function(child) {
    return child.parentid == parent.id;
  });

  if (childrenArray.length > 0) {
    var childrenObject = {};
    // Transform children into a hash/object keyed on token
    childrenArray.forEach(function(child) {
      childrenObject[child.id] = child;
    });
    if (parent.id == 0) {
      tree = childrenObject;
    } else {
      parent['children'] = childrenObject;
    }
    childrenArray.forEach(function(child) {
      unflattenToObject(array, child);
    })
  }

  return tree;
};

var arr = [
    {'id':1 ,'parentid': 0},
    {'id':2 ,'parentid': 1},
    {'id':3 ,'parentid': 1},
    {'id':4 ,'parentid': 2},
    {'id':5 ,'parentid': 0},
    {'id':6 ,'parentid': 0},
    {'id':7 ,'parentid': 4}
];
tree = unflattenToObject(arr);
0

This is a modified version of the above that works with multiple root items, I use GUIDs for my ids and parentIds so in the UI that creates them I hard code root items to something like 0000000-00000-00000-TREE-ROOT-ITEM

var tree = unflatten(records, "TREE-ROOT-ITEM");

function unflatten(records, rootCategoryId, parent, tree){
    if(!_.isArray(tree)){
        tree = [];
        _.each(records, function(rec){
            if(rec.parentId.indexOf(rootCategoryId)>=0){        // change this line to compare a root id
            //if(rec.parentId == 0 || rec.parentId == null){    // example for 0 or null
                var tmp = angular.copy(rec);
                tmp.children = _.filter(records, function(r){
                    return r.parentId == tmp.id;
                });
                tree.push(tmp);
                //console.log(tree);
                _.each(tmp.children, function(child){
                    return unflatten(records, rootCategoryId, child, tree);
                });
            }
        });
    }
    else{
        if(parent){
            parent.children = _.filter(records, function(r){
                return r.parentId == parent.id;
            });
            _.each(parent.children, function(child){
                return unflatten(records, rootCategoryId, child, tree);
            });
        }
    }
    return tree;
}
0

Copied from the Internet http://jsfiddle.net/stywell/k9x2a3g6/

    function list2tree(data, opt) {
        opt = opt || {};
        var KEY_ID = opt.key_id || 'ID';
        var KEY_PARENT = opt.key_parent || 'FatherID';
        var KEY_CHILD = opt.key_child || 'children';
        var EMPTY_CHILDREN = opt.empty_children;
        var ROOT_ID = opt.root_id || 0;
        var MAP = opt.map || {};
        function getNode(id) {
            var node = []
            for (var i = 0; i < data.length; i++) {
                if (data[i][KEY_PARENT] == id) {
                    for (var k in MAP) {
                        data[i][k] = data[i][MAP[k]];
                    }
                    if (getNode(data[i][KEY_ID]) !== undefined) {
                        data[i][KEY_CHILD] = getNode(data[i][KEY_ID]);
                    } else {
                        if (EMPTY_CHILDREN === null) {
                            data[i][KEY_CHILD] = null;
                        } else if (JSON.stringify(EMPTY_CHILDREN) === '[]') {
                            data[i][KEY_CHILD] = [];
                        }
                    }
                    node.push(data[i]);
                }
            }
            if (node.length == 0) {
                return;
            } else {
                return node;
            }
        }
        return getNode(ROOT_ID)
    }

    var opt = {
        "key_id": "ID",              //节点的ID
        "key_parent": "FatherID",    //节点的父级ID
        "key_child": "children",     //子节点的名称
        "empty_children": [],        //子节点为空时,填充的值  //这个参数为空时,没有子元素的元素不带key_child属性;还可以为null或者[],同理
        "root_id": 0,                //根节点的父级ID
        "map": {                     //在节点内映射一些值  //对象的键是节点的新属性; 对象的值是节点的老属性,会赋值给新属性
            "value": "ID",
            "label": "TypeName",
        }
    };
0

You can use npm package array-to-tree https://github.com/alferov/array-to-tree. It's convert a plain array of nodes (with pointers to parent nodes) to a nested data structure.

Solves a problem with conversion of retrieved from a database sets of data to a nested data structure (i.e. navigation tree).

Usage:

var arrayToTree = require('array-to-tree');

var dataOne = [
  {
    id: 1,
    name: 'Portfolio',
    parent_id: undefined
  },
  {
    id: 2,
    name: 'Web Development',
    parent_id: 1
  },
  {
    id: 3,
    name: 'Recent Works',
    parent_id: 2
  },
  {
    id: 4,
    name: 'About Me',
    parent_id: undefined
  }
];

arrayToTree(dataOne);

/*
 * Output:
 *
 * Portfolio
 *   Web Development
 *     Recent Works
 * About Me
 */
0

You can use this "treeify" package from Github here or NPM.

Installation:

$ npm install --save-dev treeify-js

0

Not the answer you're looking for? Browse other questions tagged or ask your own question.