Build tree array from flat array in javascript

Question

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

User · Answer

You can use this  treeify  package from Github here or NPM   Installation     npm install --save-dev treeify-js

User · Answer

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  gt  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

User · Answer

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   gt        item       const listToTree   list   gt      const map         const roots          list forEach  v  i    gt        map v id    i      list i  children                list forEach v   gt   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

User · Answer

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  lt  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  lt  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

User · Answer

My typescript solution  maybe it helps you   type ITreeItem lt T gt    T  amp        children  ITreeItem lt T gt         type IItemKey   string   number   function createTree lt T gt       flatList  T        idKey  IItemKey      parentKey  IItemKey     ITreeItem lt T gt          const tree  ITreeItem lt T gt                  hash table      const mappedArr           flatList forEach el   gt            const elId  IItemKey   el idKey            mappedArr elId    el          mappedArr elId  children                       also you can use Object values mappedArr  forEach            but if you have element which was nested more than one time        you should iterate flatList again      flatList forEach  elem  ITreeItem lt T gt     gt            const mappedElem   mappedArr elem idKey             if  elem parentKey                 mappedArr elem parentKey   children push elem             else               tree push mappedElem                          return tree      Example of usage   createTree yourListData   id    parentId

User · Answer

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

User · Answer

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   amp  amp   a k  children  a k  children      concat v              result  0       value

User · Answer

x000D   x000D  var data      country   india   gender   male   type   lower   class   X    x000D       country   china   gender   female   type   upper    x000D       country   india   gender   female   type   lower    x000D       country   india   gender   female   type   upper     x000D  var seq     country   type   gender   class    x000D  var treeData   createHieArr data seq   x000D  console log treeData  x000D  function createHieArr data seq   x000D   var hieObj   createHieobj data seq 0   x000D    hieArr   convertToHieArr hieObj  Top Level    x000D    return    name    Top Level    parent    null   x000D            children    hieArr   x000D   function convertToHieArr eachObj parent   x000D    var arr       x000D    for var i in eachObj   x000D     arr push   name  i  parent  parent  children  convertToHieArr eachObj i  i    x000D      x000D    return arr  x000D     x000D   function createHieobj data seq ind   x000D    var s   seq ind   x000D    if s    undefined   x000D     return     x000D      x000D    var childObj       x000D    for var ele of data   x000D     if ele s     undefined   x000D      if childObj ele s      undefined   x000D       childObj ele s         x000D        x000D      childObj ele s   push ele   x000D       x000D      x000D    ind   ind 1  x000D    for var ch in childObj   x000D     childObj ch    createHieobj childObj ch  seq ind  x000D      x000D    return childObj  x000D     x000D    x000D   x000D   x000D

User · Answer

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

User · Answer

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    x000D   x000D  function getTree data  root    x000D      var o       x000D      data forEach function  a    x000D          if  o a id   amp  amp  o a id  children    x000D              a children   o a id  children  x000D            x000D          o a id    a  x000D          o a parentId    o a parentId         x000D          o a parentId  children   o a parentId  children        x000D          o a parentId  children push a   x000D          x000D      return o root  children  x000D    x000D   x000D  var 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       x000D      tree   Object keys data  reduce function  r  k    x000D          r k    getTree data k    0    x000D          return r  x000D              x000D   x000D  console log tree   x000D   as-console-wrapper   max-height  100   important  top  0    x000D   x000D   x000D

User · Answer

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   gt  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  quot dummy quot  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

User · Answer

ES6 Map version   getTreeData    items    gt      if  items  amp  amp  items length  gt  0        const data           const map           items map  item    gt          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  amp  amp            typeof map mappedElem parentId       quot undefined quot                        map mappedElem parentId  children push mappedElem             else             data push mappedElem                               return data        return             use like this    const treeData   getTreeData flatList

User · Answer

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  lt  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

User · Answer

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  gt  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

User · Answer

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   gt  entity parent id    parent id     if   isEmpty  children          if   parent id    null           tree   children       else         parent  children     children           children map  child   gt  unflattenEntities  entities  child            return tree

User · Answer

You can handle this question with just two line coding     flatArray  forEach f  gt              f nodes   flatArray  filter g  gt g parentId  f id  value        var resultArray   flatArray  filter f  gt f parentId  null  value      Test Online  see the browser console for created tree   Requirements   1- Install lodash 4  a Javascript library for manipulating objects and collections with performant methods    like the Linq in c   Lodash  2- A flatArray like below       var flatArray               id 1 parentId null text  parent1  nodes                      id 2 parentId null text  parent2  nodes                            id 3 parentId 1 text  childId3Parent1  nodes                            id 4 parentId 1 text  childId4Parent1  nodes                            id 5 parentId 2 text  childId5Parent2  nodes                            id 6 parentId 2 text  childId6Parent2  nodes                            id 7 parentId 3 text  childId7Parent3  nodes                            id 8 parentId 5 text  childId8Parent5  nodes              Thank Mr  Bakhshabadi  Good luck

User · Answer

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    gt  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    gt                item children   tempChild item id                     if  item children length                    item children forEach  child  Folder    gt                        addChildren child                                                         const tempChild  any               flatData forEach  item  Folder    gt                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    gt                addChildren base                       return tree

User · Answer

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   quot id quot           parentId   quot parentId quot           childrenKey   quot children quot              options            const copiesById   data reduce           copies  datum    gt    copies datum id     datum   amp  amp  copies                         return Object values copiesById  reduce           root  datum    gt                if   datum parentId   amp  amp  copiesById datum parentId                       copiesById datum parentId   childrenKey         copiesById datum parentId   childrenKey   datum                  else                   root        root  datum                              return root                         const data                    quot account quot    quot 10 quot            quot name quot    quot Konto 10 quot            quot parentAccount quot   null                  quot account quot    quot 1010 quot            quot name quot    quot Konto 1010 quot            quot parentAccount quot    quot 10 quot                   quot account quot    quot 10101 quot            quot name quot    quot Konto 10101 quot            quot parentAccount quot    quot 1010 quot                   quot account quot    quot 10102 quot            quot name quot    quot Konto 10102 quot            quot parentAccount quot    quot 1010 quot                   quot account quot    quot 10103 quot            quot name quot    quot Konto 10103 quot            quot parentAccount quot    quot 1010 quot                   quot account quot    quot 20 quot            quot name quot    quot Konto 20 quot            quot parentAccount quot   null                  quot account quot    quot 2020 quot            quot name quot    quot Konto 2020 quot            quot parentAccount quot    quot 20 quot                   quot account quot    quot 20201 quot            quot name quot    quot Konto 20201 quot            quot parentAccount quot    quot 2020 quot                   quot account quot    quot 20202 quot            quot name quot    quot Konto 20202 quot            quot parentAccount quot    quot 2020 quot            const options         id   quot account quot       parentId   quot parentAccount quot       childrenKey   quot children quot      console log       quot Hierarchical tree quot       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  quot childNodes quot      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

User · Answer

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    gt   map  filter arr  ar   gt   ar parentIdKey    ar   gt          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

User · Answer

Use this ES6 approach  Works like charm    x000D   x000D     Data Set x000D     One top level comment  x000D  const comments      x000D      id  1  x000D      parent id  null x000D       x000D      id  2  x000D      parent id  1 x000D       x000D      id  3  x000D      parent id  1 x000D       x000D      id  4  x000D      parent id  2 x000D       x000D      id  5  x000D      parent id  4 x000D      x000D   x000D  const nest    items  id   null  link    parent id     gt  x000D    items x000D       filter item   gt  item link      id  x000D       map item   gt        item  children  nest items  item id       x000D   x000D  console log  x000D    nest comments  x000D    x000D   x000D   x000D

User · Answer

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  lt  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

User · Answer

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    x000D   x000D   var arr     x000D            id  1   parentid    0   x000D            id  4   parentid    2   x000D            id  3   parentid    1   x000D            id  5   parentid    0   x000D            id  6   parentid    0   x000D            id  2   parentid    1   x000D            id  7   parentid    4   x000D            id  8   parentid    1  x000D           x000D      function unflatten arr    x000D        var tree       x000D            mappedArr       x000D            arrElem  x000D            mappedElem  x000D   x000D           First map the nodes of the array to an object - gt  create a hash table  x000D        for var i   0  len   arr length  i  lt  len  i      x000D          arrElem   arr i   x000D          mappedArr arrElem id    arrElem  x000D          mappedArr arrElem id   children         x000D          x000D   x000D   x000D        for  var id in mappedArr    x000D          if  mappedArr hasOwnProperty id     x000D            mappedElem   mappedArr id   x000D               If the element is not at the root level  add it to its parent array of children  x000D            if  mappedElem parentid    x000D              mappedArr mappedElem  parentid     children   push mappedElem   x000D              x000D               If the element is at the root level  add it to first level elements array  x000D            else   x000D              tree push mappedElem   x000D              x000D            x000D          x000D        return tree  x000D        x000D   x000D  var tree   unflatten arr   x000D  document body innerHTML     lt pre gt      JSON stringify tree  null        x000D   x000D   x000D    JS Fiddle  Flat Array to Tree

User · Answer

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     gt  arr reduce  o  n    gt       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 gt 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    gt  el append tree reduce  ul  n    gt      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    x000D   x000D  const getTree    arr  p    parent id     gt  arr reduce  o  n    gt    x000D    if   o n id   o n id        x000D    if   o n p    o n p         x000D    if   o n p   nodes  o n p   nodes       x000D    if  o n id  nodes  n nodes   o n id  nodes  x000D    o n p   nodes push n   x000D    o n id    n  x000D    return o  x000D          x000D   x000D   x000D  const treeToHTML    tree  el  cb    gt  el append tree reduce  ul  n    gt    x000D    const li   document createElement  li    x000D    if  cb  cb call li  n   x000D    if  n nodes  length  treeToHTML n nodes  li  cb   x000D    ul append li   x000D    return ul  x000D     document createElement  ul      x000D   x000D   x000D     DEMO TIME  x000D   x000D  const nodesList     x000D     id  10   parent id  4   text   Item 10       PS  Order does not matters x000D     id  1    parent id  0   text   Item 1      x000D     id  4    parent id  0   text   Item 4    x000D     id  3    parent id  5   text   Item 3    x000D     id  5    parent id  4   text   Item 5    x000D     id  2    parent id  1   text   Item 2    x000D     x000D  const myTree   getTree nodesList  0  nodes     Get nodes of Root  0  x000D   x000D  treeToHTML myTree  document querySelector   tree    function node    x000D    this textContent       node parent id    node id     node text    x000D    this  node   node  x000D    this addEventListener  click   clickHandler   x000D      x000D   x000D  function clickHandler ev    x000D    if  ev target     this  return  x000D    console clear    x000D    console log this  node id   x000D     x000D   lt div id  tree  gt  lt  div gt  x000D   x000D   x000D

User · Answer

Answer to a similar question  https   stackoverflow com a 61575152 7388356 UPDATE You can use Map object introduced in ES6  Basically instead of finding parents by iterating over the array again  you ll just get the parent item from the array by parent s id like you get items in an array by index  Here is the simple example  const people             id   quot 12 quot       parentId   quot 0 quot       text   quot Man quot       level   quot 1 quot       children  null              id   quot 6 quot       parentId   quot 12 quot       text   quot Boy quot       level   quot 2 quot       children  null              id   quot 7 quot       parentId   quot 12 quot       text   quot Other quot       level   quot 2 quot       children  null              id   quot 9 quot       parentId   quot 0 quot       text   quot Woman quot       level   quot 1 quot       children  null              id   quot 11 quot       parentId   quot 9 quot       text   quot Girl quot       level   quot 2 quot       children  null         function toTree arr      let arrMap   new Map arr map item   gt   item id  item       let tree          for  let i   0  i  lt  arr length  i          let item   arr i        if  item parentId      quot 0 quot           let parentItem   arrMap get item parentId          if  parentItem            let   children     parentItem           if  children              parentItem children push item             else             parentItem children    item                           else         tree push item                return tree     let tree   toTree people    console log tree

User · Answer

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   x000D   x000D     Example usage x000D  var arr     x000D        id  1   parentid    0   x000D        id  2   parentid    1   x000D        id  3   parentid    1   x000D        id  4   parentid    2   x000D        id  5   parentid    0   x000D        id  6   parentid    0   x000D        id  7   parentid    4  x000D     x000D   x000D  unflatten   function  array  parent  tree    x000D      tree   typeof tree      undefined    tree       x000D      parent   typeof parent      undefined    parent     id  0    x000D           x000D      var children     filter  array  function child   return child parentid    parent id      x000D       x000D      if     isEmpty  children       x000D          if  parent id    0    x000D             tree   children     x000D           else  x000D             parent  children     children x000D            x000D            each  children  function  child    unflatten  array  child                            x000D        x000D       x000D      return tree  x000D    x000D   x000D  tree   unflatten  arr    x000D  document body innerHTML     lt pre gt      JSON stringify tree  null        x000D   lt script src  https   cdnjs cloudflare com ajax libs underscore js 1 9 1 underscore-min js  gt  lt  script gt  x000D   x000D   x000D    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

User · Answer

Incase anyone needs it for multiple parent   Refer id 2 which has multiple parents  x000D   x000D    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    Chelm            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   Chelm                    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   Chelm                    Name   Scarlet                    childNodes                                                                    const createDataTree   dataset   gt          const hashTable   Object create null         dataset forEach aData   gt  hashTable aData ID        aData  childNodes              const dataTree             dataset forEach Datae   gt              if  Datae parentID   amp  amp  Datae parentID length  gt  0                  Datae parentID forEach  aData   gt                    hashTable aData  childNodes push hashTable Datae ID                                 else          dataTree push hashTable Datae ID                                      return dataTree                     window alert JSON stringify createDataTree dataSet     x000D   x000D   x000D

User · Answer

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 amp script js amp output  FurkanO s solution seems to be the fastest    x000D   x000D     x000D     performance test for https   stackoverflow com questions 18017869 build-tree-array-from-flat-array-in-javascript x000D     x000D   x000D     Data Set  e g  nested comments  x000D  var comments      x000D      id  1  x000D      parent id  null x000D       x000D      id  2  x000D      parent id  1 x000D       x000D      id  3  x000D      parent id  4 x000D       x000D      id  4  x000D      parent id  null x000D       x000D      id  5  x000D      parent id  4 x000D      x000D   x000D     add some random entries x000D  let maxParentId   10000  x000D  for  let i 6  i lt  maxParentId  i    x000D    x000D    let randVal   Math floor  Math random     maxParentId    1   x000D    comments push   x000D      id  i  x000D      parent id   randVal   200     0   null   randVal  x000D        x000D    x000D   x000D     solution from user  shekhardtu   https   stackoverflow com a 55241491 5135171  x000D  const nest    items  id   null  link    parent id     gt  x000D    items x000D       filter item   gt  item link      id  x000D       map item   gt        item  children  nest items  item id       x000D    x000D   x000D     solution from user  FurkanO   https   stackoverflow com a 40732240 5135171  x000D  const createDataTree   dataset   gt    x000D      let hashTable   Object create null  x000D      dataset forEach  aData   gt  hashTable aData id         aData  children          x000D      let dataTree      x000D      dataset forEach  aData   gt    x000D        if  aData parent id   hashTable aData parent id  children push hashTable aData id   x000D        else dataTree push hashTable aData id   x000D          x000D      return dataTree x000D     x000D   x000D   x000D     x000D     lets evaluate the timing for both methods x000D     x000D  let t0   performance now    x000D  let createDataTreeResult   createDataTree comments   x000D  let t1   performance now    x000D  console log  Call to createDataTree took     Math floor t1 - t0      milliseconds     x000D   x000D  t0   performance now    x000D  let nestResult   nest comments   x000D  t1   performance now    x000D  console log  Call to nest took     Math floor t1 - t0      milliseconds     x000D   x000D   x000D   x000D   x000D    console log nestResult   x000D    console log createDataTreeResult   x000D   x000D     bad  but simple way of comparing object equality x000D  console log JSON stringify nestResult    JSON stringify createDataTreeResult    x000D   x000D   x000D

User · Answer

BONUS1   NODES MAY or MAY NOT BE ORDERED     BONUS2   NO 3RD PARTY LIBRARY NEEDED  PLAIN JS     BONUS3   User  quot Elias Rabl quot  says this is the fastest solution  see his answer below    Here it is  const createDataTree   dataset   gt      const hashTable   Object create null     dataset forEach aData   gt  hashTable aData ID        aData  childNodes          const dataTree         dataset forEach aData   gt        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        gt      const dataSet           quot ID quot   1       quot Phone quot    quot  403  125-2552 quot        quot City quot    quot Coevorden quot        quot Name quot    quot Grady quot              quot ID quot   2       quot parentID quot   1       quot Phone quot    quot  979  486-1932 quot        quot City quot    quot Chelm quot        quot Name quot    quot Scarlet quot           const expectedDataTree           quot ID quot   1       quot Phone quot    quot  403  125-2552 quot        quot City quot    quot Coevorden quot        quot Name quot    quot Grady quot       childNodes            quot ID quot   2         quot parentID quot   1         quot Phone quot    quot  979  486-1932 quot          quot City quot    quot Chelm quot          quot Name quot    quot Scarlet quot         childNodes                      expect createDataTree dataSet   toEqual expectedDataTree

User · Answer

without third party library no need for pre-ordering array you can get any portion of the tree you want   Try this  function getUnflatten arr parentid     let output        for const obj of arr       if obj parentid    parentid         let children   getUnflatten arr obj id         if children length           obj children   children               output push obj               return output      Test it on Jsfiddle

User · Answer

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   x000D   x000D  function list to tree list      var map       node  roots       i       for  i   0  i  lt  list length  i    1        map list i  id    i     initialize the map     list i  children          initialize the children          for  i   0  i  lt  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    x000D   x000D   x000D   If you re into complexity theory this solution is T n log n    The recursive-filter solution is T n 2  which can be a problem for large data sets

User · Answer

This is an old thread but I figured an update never hurts  with ES6 you can do   x000D   x000D  const data          id  1      parent id  0          id  2      parent id  1          id  3      parent id  1          id  4      parent id  2          id  5      parent id  4          id  8      parent id  7          id  9      parent id  8          id  10      parent id  9      const arrayToTree    items     id   null  link    parent id     gt  items filter item   gt  id  null    items some ele  gt ele id   item link     item link      id   map item   gt        item  children  arrayToTree items  item id      const temp1 arrayToTree data  console log temp1   const treeToArray    items     key    children     gt  items reduce  acc  curr    gt      acc     treeToArray curr key    map        key     child     ele      gt  ele   items   const temp2 treeToArray temp1   console log temp2  x000D   x000D   x000D   hope it helps someone

[javascript] Build tree array from flat array in javascript

Examples related to javascript

Examples related to arrays

Examples related to list

Examples related to tree