Convert an Array to Tree in Typescript

Question

I have structure database in array of objects stored like this:

 arry = [{"name": "a", "id": "2", "data":"foo", "parent": "1"},
 {"name": "b", "id": "3", "data":"foo", "parent": "2"},
 {"name": "c", "id": "4", "data":"foo", "parent": "3"},
 {"name": "d", "id": "5", "data":"foo", "parent": "3"},
 {"name": "e", "id": "6", "data":"foo", "parent": "4"},
 {"name": "f", "id": "7", "data":"foo", "parent": "5"}]

I want nested structure like this

{
"2":{
   "name": "a",
   "data": "foo",
  "3":{
     "name": "b",
     "data":"foo",
     "4":{
        "name": "c",
        "data":"foo",
        "6":{
           "name": "e",
           "data": "foo",
          };
       },
      "5":{
         "name": "d",
         "data": "foo",
         "7":{
            "name": "f",
            "data": "foo"
           }
        }
      }
    }
  };

so I can use it Angular Material tree.

This is more of a programming problem than an angular one. Also, what is your data source for the table, can you guarantee that there wont be any cycles? — user8401765
– user8401765, Commented Oct 17, 2018 at 5:43

Kaiido · Accepted Answer · 2018-10-17 05:44:47Z

5

To do this, you can reduce your array of nodes to a dictionary, using each node's id as index.

This way, you'll have all the nodes accessible by their id directly on the dictionary. You'll thus be able to store each node in its parent easily.

Once all the nodes are stored in their respective parent, you just have to grab the root node from the dictionary, it will hold all your tree.

It may happen that the parent isn't yet in the dictionary when you parse the child, in this case, you can use a dummy object that will play a placeholder the time we come to parse the actual parent node.

var arry = [
 {"name": "a", "id": "2", "data":"foo", "parent": "1"},
 {"name": "b", "id": "3", "data":"foo", "parent": "2"},
 {"name": "c", "id": "4", "data":"foo", "parent": "3"},
 {"name": "d", "id": "5", "data":"foo", "parent": "3"},
 {"name": "e", "id": "6", "data":"foo", "parent": "4"},
 {"name": "f", "id": "7", "data":"foo", "parent": "5"}
];

function totree(branches, node) {
  // if we don't have the parent yet
  if (!branches[node.parent]) {
    // create a dummy placeholder for now
    branches[node.parent] = {};
  }
  // store our node in its parent
  branches[node.parent][node.id] = node;
  // store our node in the full list
  // copy all added branches on possible placeholder
  branches[node.id] = Object.assign(node, branches[node.id]);

  return branches;
}

var tree = arry.reduce(totree, {})['1']; // get only the root node ('1')

console.log(tree);

answered Oct 17, 2018 at 5:44

Kaiido

139k15 gold badges266 silver badges333 bronze badges

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

8 Comments

AsGoodAsItGets Over a year ago

Although this solution is elegant, it does not solve the generic case when a tree can have multiple root nodes. We'd still have to iterate through the dictionary to create the final structure.

Kaiido Over a year ago

@AsGoodAsItGets althought there are graphs with no root node, a tree always has a single one.

AsGoodAsItGets Over a year ago

@Kaiido I assume you're refering to the tree data structure. I'm refering to the generic use of trees as hierarchical UI elements, in which case of course you can have multiple roots. We are not talking about graph data structures.

AsGoodAsItGets Over a year ago

And to answer the original question, a complete and far more elegant ES6-only solution is this one: stackoverflow.com/a/55241491/134120

Kaiido Over a year ago

@AsGoodAsItGets hum... please re-read the question here. Yes we are exactly talking about Graph data structure here. And sorry but recursive approach building a lot of mess in the GC is not what I call an "elegant" solution, even though it's done writing a bit less characters (is it really btw?).

|

Collectives™ on Stack Overflow

Convert an Array to Tree in Typescript

1 Answer 1

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related