Creating tree object from flat array

Question

I am a little stuck on this. I want to create a tree structure from a flat array. Say I have this input:

var input = [
    ["a","b","c"],
    ["a", "b","d"],
    ["e","f","g"],
];

I want to create a tree structure looking like the following:

// output:
[
    {
        id: "a",
        children: [
            {id: "b", children: [
                {id: "c", children: []},
                {id: "d", children: []}
            ]},
        ] 
    },
    { 
        id: "e",
        children: [
          {
              id: "f",
              children: [{ id: "g", children: []}]
          },
        ]
    }
]

One way I was thinking of doing this was having a map of all of the parent and iterate through the input array to set the parent to child mappings. But I come to problems when trying to actually construct the tree object from that map and avoiding duplicates. Any pointers are appreciated, thanks!

Start with the innermost object then add those objects to the next level up, then add that object to the level above it. — Jordan
– Jordan, Commented Aug 3, 2015 at 19:04
@Jordan So essentially create the tree by iterating from right to left on each item? — thunderousNinja
– thunderousNinja, Commented Aug 3, 2015 at 19:11
I suppose you could think of it that way. But, basically what i'm saying is create your inner arrays, then add that group to the array above it using array.push. — Jordan
– Jordan, Commented Aug 3, 2015 at 19:13

Community · Accepted Answer · 2017-05-23 12:10:36Z

I found the solution to a problem that is similar to your question.

_makeTree

If you have data that looks like this:

_makeTree({ q:
    [
        {"id": 123, "parentid": 0, "name": "Mammals"},
        {"id": 456, "parentid": 123, "name": "Dogs"},
        {"id": 214, "parentid": 456, "name": "Labradors"},
        {"id": 810, "parentid": 456, "name": "Pugs"},
        {"id": 919, "parentid": 456, "name": "Terriers"}
    ]
});

Parameters:

q (Array): A query result (see example below)
id (String): The name of the id column (Default: "id")
parentid (String): The name of the ParentItemID column (Default: "parentid")
children (String): The name of the "children" array to be created in rows that have children (Default: "children")

Then result should be something like the following structure:

[
    {
        "id": 123,
        "parentid": 0,
        "name": "Mammals",
        "children": [
            {
                "id": 456,
                "parentid": 123,
                "name": "Dogs",
                "children": [
                    {
                        "id": 214,
                        "parentid": 456,
                        "name": "Labradors"
                    },
                    {
                        "id": 810,
                        "parentid": 456,
                        "name": "Pugs"
                    },
                    {
                        "id": 919,
                        "parentid": 456,
                        "name": "Terriers"
                    }
                ]
            }
        ]
    }
]

Now, _makeTree codes:

var _makeTree = function(options) {
  var children, e, id, o, pid, temp, _i, _len, _ref;
  id = options.id || "id";
  pid = options.parentid || "parentid";
  children = options.children || "children";
  temp = {};
  o = [];
  _ref = options.q;
  for (_i = 0, _len = _ref.length; _i < _len; _i++) {
    e = _ref[_i];
    temp[e[id]] = e;
    if (temp[e[pid]] != null) {
      if (temp[e[pid]][children] == null) {
        temp[e[pid]][children] = [];
      }
      temp[e[pid]][children].push(e);
    } else {
      o.push(e);
    }
  }
  return o;
};

References:

I need to create a custom tree data-structure using JavaScript

Creating trees from SQL queries in Javascript

_makeTree library

Keep in mind that this answer does require your items to be sorted (so that parents always come before their children. Since I could not find a npm module which implements an O(n) solution without that restriction, 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

Collectives™ on Stack Overflow

Creating tree object from flat array

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related