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!

Improve this question
0

2 Answers 2

Reset to default
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

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

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
@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 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.
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: github.com/philipstanislaus/array-to-tree-benchmarks . Happy to add others if you are interested!
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
|
10

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.