27

I have a list of "page" objects with a parent field. This parent field references another object in the list. I would like to create a tree hierarchy from this list based on this field.

Here is what my original list looks like:

[
  {
    id: 1,
    title: 'home',
    parent: null
  },
  {
    id: 2,
    title: 'about',
    parent: null
  },
  {
    id: 3,
    title: 'team',
    parent: 2
  },
  {
    id: 4,
    title: 'company',
    parent: 2
  }
]

I would like to convert it into a tree structure like this:

[
  {
    id: 1,
    title: 'home',
    parent: null
  },
  {
    id: 2,
    title: 'about',
    parent: null,
    children:  [
      {
        id: 3,
        title: 'team',
        parent: 2
      },
      {
        id: 4,
        title: 'company',
        parent: 2
      }
    ]
]

I was hoping for a reusable function that I can call against an arbitrary list any time. Anyone know of a good way to handle this? Any help or advice would be greatly appreciated!

TruMan1
  • 33,665
  • 59
  • 184
  • 335

2 Answers2

69
function treeify(list, idAttr, parentAttr, childrenAttr) {
    if (!idAttr) idAttr = 'id';
    if (!parentAttr) parentAttr = 'parent';
    if (!childrenAttr) childrenAttr = 'children';

    var treeList = [];
    var lookup = {};
    list.forEach(function(obj) {
        lookup[obj[idAttr]] = obj;
        obj[childrenAttr] = [];
    });
    list.forEach(function(obj) {
        if (obj[parentAttr] != null) {
            if (lookup[obj[parentAttr]] !== undefined) {
                lookup[obj[parentAttr]][childrenAttr].push(obj);
            } else {
                 //console.log('Missing Parent Data: ' + obj[parentAttr]);
                 treeList.push(obj);
            }               
        } else {
            treeList.push(obj);
        }
    });
    return treeList;
};

Fiddle

Enkode
  • 4,515
  • 4
  • 35
  • 50
Amadan
  • 191,408
  • 23
  • 240
  • 301
  • 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 – Philip Stanislaus May 07 '17 at 17:34
  • 1
    @PhilipStanislaus: `O(2n) = O(n)`. My solution is also `O(n)`. I admit that I wasn't going the speed record. Whether my version or yours is faster can be measured (two simple loops vs one complex one), but I can't tell a priori which is faster. However, their time complexity is *exactly the same*. – Amadan May 07 '17 at 18:53
  • @Amadan thanks for your thoughts. You are right that their time complexity is equal. I posted the link just in case someone is interested in a efficient implementation in an npm package. – Philip Stanislaus May 07 '17 at 18:59
  • 1
    Since I received quite a lot of downloads for my npm package `performant-array-to-tree`, I wrote some benchmark tests of some available packages on npm. Please find the results here: https://github.com/philipstanislaus/array-to-tree-benchmarks . Happy to add others if you are interested! – Philip Stanislaus Aug 13 '19 at 12:47
  • Can you update to handle a slight variant? In this case there is no parent id. Rather it is assumed that if the depth is lower or the same as the previous list element its parent is its predecessor – SumNeuron May 18 '22 at 14:22
  • @SumNeuron StackOverflow rules: one question per question. Ask a new question, though as part of what solutions you considered feel free to link here. – Amadan May 18 '22 at 15:00
  • @Amadan here ya go https://stackoverflow.com/questions/72292676/javascript-flat-list-to-tree-without-parent-id – SumNeuron May 18 '22 at 16:15
  • I know this question is a bit old, but I was just wondering if anyone could explain this solution in english? I'd like to port this solution to c#, and I don't know js enough to read this – Skye Bleed Jul 11 '22 at 12:40
  • @SkyeBleed I believe Rob's answer on this same question is basically exactly what you want, a simplification and explanation of my algorithm. If there is anything specific you want to know, feel free to ask. The only JS-specific things in Rob's answer should be: the `arr.forEach((o) => {` syntax, which is basically C#'s `foreach (o in arr) {`, `[]` which is like an empty ArrayList, and `{}` which is like an empty Hashtable. – Amadan Jul 12 '22 at 02:16
  • @Amadan thank you, this was very helpful! I wrote it out and I think the problem I'm having is that c# copies values instead of moving them, so the children of children don't get carried over unless I keep adding new loops, which is obviously unsustainable. can I ask how you would handle that? I've tried using recursion but it's not working correctly. – Skye Bleed Jul 13 '22 at 13:17
  • This code does not use recursion though...? and I have no idea what you mean by "moving values". Anyway, it is hard speaking in hypotheticals, and it is off-topic here. Please try to translate it yourself, and if it does not work, post a question, with a link refering to this answer; if you want you can also comment the new question link here and I'll take a look (even though I am not a c# expert). – Amadan Jul 14 '22 at 01:34
9

The accepted answer was very helpful in my research, but, I had to mentally parse the id params which I understand make the function more flexible, but perhaps a bit harder to reason about for someone new to the algorithm.

In case someone else is has this difficulty, here's essentially the same code, but maybe easier to grok:

const treeify = (arr, pid) => {
  const tree = [];
  const lookup = {};
  // Initialize lookup table with each array item's id as key and 
  // its children initialized to an empty array 
  arr.forEach((o) => {
    lookup[o.id] = o;
    lookup[o.id].children = [];
  });
  arr.forEach((o) => {
    // If the item has a parent we do following:
    // 1. access it in constant time now that we have a lookup table
    // 2. since children is preconfigured, we simply push the item
    if (o.parent !== null) {
      lookup[o.parent].children.push(o);
    } else {
      // no o.parent so this is a "root at the top level of our tree
      tree.push(o);
    }
  });
  return tree;
};

It's the same code as accepted answer with some comments to explain what's going on. Here is a use case for this which will result in a list of divs rendered to page with inline marginLeft indentation based on the level:

const arr = [
  {id: 1, title: 'All', parent: null},
  {id: 2, title: 'Products', parent: 1},
  {id: 3, title: 'Photoshop', parent: 2},
  {id: 4, title: 'Illustrator', parent: 2},
  {id: 4, title: 'Plugins', parent: 3},
  {id: 5, title: 'Services', parent: 1},
  {id: 6, title: 'Branding', parent: 5},
  {id: 7, title: 'Websites', parent: 5},
  {id: 8, title: 'Pen Testing', parent: 7}];
const render = (item, parent, level) => {
  const div = document.createElement('div');
  div.textContent = item.title;
  div.style.marginLeft = level * 8 + 'px';
  parent.appendChild(div);
  if (item.children.length) {
    item.children.forEach(child => render(child, div, ++level));
  }
  return parent;
}
const fragment = document.createDocumentFragment();
treeify(arr)
  .map(item => render(item, fragment, 1))
  .map(frag => document.body.appendChild(frag))

Codepen if you'd like to run it: https://codepen.io/roblevin/pen/gVRowd?editors=0010

To my mind, the interesting part about this solution is that the lookup table remains flat using the IDs of the items as keys, and only the root object(s) get pushed into the resulting tree list. However, due to the referential nature of JavaScript objects, the root has its children, and children their children, and so on, but it's essentially connected from the root and hence tree-like.

Rob
  • 4,093
  • 5
  • 44
  • 54