Build Tree Array from Flat Array in JavaScript

Build tree array from flat array in javascript

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.

function list_to_tree(list) {
  var map = {}, node, roots = [], i;
  
  for (i = 0; i < list.length; i += 1) {
    map[list[i].id] = i; // initialize the map
    list[i].children = []; // initialize the children
  }
  
  for (i = 0; i < 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));

Build Tree Structure of the given flat array

You could take an iterative approach by finding the wanted name of a given level.

If not found take a new object and take this object for the next level.

const
    data = [{ L0: "India", L0_ID: "IN", L1: "Karnataka", L1_ID: "KA", L2: "BLR", L3: "Mysore", L4: "CHB" }, { L0: "India", L0_ID: "IN", L1: "Karnataka", L1_ID: "KA", L2: "BLR", L3: "Hubli" }, { L0: "India", L0_ID: "IN", L1: "Karnataka", L1_ID: "KA", L2: "BLR", L3: "Udupi" }, { L0: "India", L0_ID: "IN", L1: "Rajasthan", L1_ID: "RJ", L2: "Jaipur", L3: "Shastri Nagar", L4: "Lane One" }, { L0: "India", L0_ID: "IN", L1: "Rajasthan", L1_ID: "RJ", L2: "Jodhpur", L3: "Shastri Nagar", L4: "Lane One" }],
    tree = data.reduce((r, o) => {
        let i = 0,
            t = { children: r };
            
        while (`L${i}` in o) {
            const
                name = o[`L${i}`],
                id = o[`L${i}_ID`] || null;
            let item = (t.children ??= []).find(q => q.name === name);
            if (!item) t.children.push(item = { name, id });
            t = item;
            i++;
        }
        return r;
    }, []);

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Build tree array from flat ordered array when only depth and NOT parent ID is known

You could take a helper array for the levels and assign the object to the latest array of the depth.

const
    items = [{ name: "1", depth: 1 }, { name: "2", depth: 1 }, { name: "2_1", depth: 2 }, { name: "2_1_1", depth: 3 }, { name: "2_1_2", depth: 3 }, { name: "2_2", depth: 2 }],
    tree = [],
    levels = [tree];

items.forEach(o =>
    levels[o.depth - 1].push({ ...o, children: levels[o.depth] = [] })
);

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Build a Tree from Flat Array

The solution I came up with was to loop through the list, splitting each resource by '.' and adding a node for each resource directory if not already within the parent node's children

const list = [
    { resource: 'User', action: 'Create', id: 1 },
    { resource: 'User', action: 'Edit', id: 2 },
    { resource: 'User', action: 'Delete', id: 3 },
    { resource: 'Utility.Rule', action: 'Create', id: 4 },
    { resource: 'Utility.Rule', action: 'Edit', id: 5 },
    { resource: 'Utility.Config', action: 'Create', id: 6 },
];

function arrayToTree(list, rootNode = { id: 'root', name: 'MyTree' }) {
    const addChild = (node, child) => ((node.children ?? (node.children = [])).push(child), child);

    for (const { id, action, resource } of list) {
        const path = resource.split('.');
        const node = path.reduce(
            (currentNode, targetNodeId) =>
                currentNode.children?.find(({ id }) => id === targetNodeId) ??
                addChild(currentNode, { id: targetNodeId, name: targetNodeId }),
            rootNode
        );
        addChild(node, { id: String(id), name: action });
    }

    return rootNode;
}

console.log(arrayToTree(list));

Create a hierarchy of arrays from a flat array

const ar = [
  {id: 1, name: "A", parent: null},
  {id: 2, name: "B", parent: 1},
  {id: 11, name: "AA", parent: 1},
  {id: 12, name: "AB", parent: 1},
  {id: 111, name: "AAA", parent: 11},
  {id: 41, name: "CC", parent: 4},
  {id: 4, name: "C", parent: 1},
];

const hierarchy = (arr) => {
  const map = {};
  let root;
  for (const ele of arr) {
    map[ele.id] = ele;
    ele.children = [];
  }
  for (const ele of arr) {
    if (map[ele.parent] != undefined)
      map[ele.parent].children.push(ele);
    else
      root = ele;
  }
  return root;
}

console.log(hierarchy(ar));

Building tree array of objects from flat array of objects

You could use a hash table and take id and pid in every loop as connected nodes.

This proposal works with unsorted data as well.

var nodes = [{ id: 6, pid: 1, name: "cace" }, { id: 1, pid: 0, name: "kpittu" }, { id: 2, pid: 0, name: "news" }, { id: 3, pid: 0, name: "menu" }, { id: 4, pid: 3, name: "node" }, { id: 5, pid: 4, name: "subnode" }],

    tree = function (data, root) {

        var r = [], o = {};

        data.forEach(function (a) {

            if (o[a.id] && o[a.id].children) {

                a.children = o[a.id] && o[a.id].children;

            }

            o[a.id] = a;

            if (a.pid === root) {

                r.push(a);

            } else {

                o[a.pid] = o[a.pid] || {};

                o[a.pid].children = o[a.pid].children || [];

                o[a.pid].children.push(a);

            }

        });

        return r;

    }(nodes, 0);

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Build tree array from flat array in Typescript / JavaScript

Here is a brute force solution to the problem:

var flat = [
{
    Id: 1,
    Text: 'What kind of apple is it?',
    Desc: '',
    ParentId: 0
},
{
    Id: 2,
    Text: 'Green Apple',
    Desc: '',
    ParentId: 1
},
{
    Id: 3,
    Text: 'Red Apple',
    Desc: '',
    ParentId: 1
},
{
    Id: 4,
    Text: 'Purple GMO Apple',
    Desc: '',
    ParentId: 1
},
{
    Id: 5,
    Text: 'What is the issue with the apple?',
    Desc: '',
    ParentId: 2
},
{
    Id: 6,
    Text: 'Spoiled.',
    Desc: '',
    ParentId: 5
},
{
    Id: 7,
    Text: 'Taste Bad.',
    Desc: '',
    ParentId: 5
},
{
    Id: 8,
    Text: 'Too Ripe.',
    Desc: '',
    ParentId: 5
},
{
    Id: 9,
    Text: 'Is not an apple.',
    Desc: '',
    ParentId: 5
},
{
    Id: 10,
    Text: 'The apple was not green.',
    Desc: '',
    ParentId: 5
},
]

// first get the roots
const tree = flat.filter((question) => question.ParentId === 0);

// Next we are going to call alternating methods recursively.
function populateQuestionChildren(node) {
  const { Id } = node;
  flat.forEach((answer) => {
    if (answer.ParentId === Id) {
      if (!node.ChildAnswers) {
        node.ChildAnswers = [];
      }
      node.ChildAnswers.push(answer);
      populateAnswerChildren(answer);
    }
  });
}

function populateAnswerChildren(node) {
  const { Id } = node;
  flat.forEach((question) => {
    if (question.ParentId === Id) {
      if (!node.ChildQuestions) {
        node.ChildQuestions = [];
      }
      node.ChildQuestions.push(question);
      populateQuestionChildren(question);
    }
  });
}

// Kick off the build for each question tree. 
tree.forEach((question) => {
  populateQuestionChildren(question);
});

It is likely that there are more elegant solutions - but given that this will be only few dozen or a few hundred question/answers - this should get you what you need.

[EDIT]

I used your interfaces and discovered a problem with my code. There is only one "ChildQuestion" on an Answer object. So here is my change to TypeScript to make it work properly. I hope it helps:

interface Question {
  Id: number;
  Text: string;
  Desc: string;
  ParentId: number;
  ChildAnswers ? : Answer[];
}

interface Answer {
  Id: number;
  Text: string;
  Desc: string;
  ParentId: number;
  ChildQuestion ? : Question;
}

// first get the roots
const tree = flat.filter((question) => question.ParentId === 0);

function populateQuestionChildren(node: Question) {
  const { Id } = node;
  flat.forEach((answer) => {
    if (answer.ParentId === Id) {
      if (!node.ChildAnswers) {
        node.ChildAnswers = [];
      }
      node.ChildAnswers.push(answer);
      populateAnswerChild(answer);
    }
  });
}

function populateAnswerChild(answer: Answer) {
  const { Id } = answer;
  // switch to every so we can break early once a question is found.
  flat.every((node) => {
    if (node.ParentId === Id) {
      answer.ChildQuestion = node;
      populateQuestionChildren(node);
      return false;
    }
    return true;
  });
}

tree.forEach((question) => {
  populateQuestionChildren(question);
});

flatten tree structure into array

Here's a solution using flatMap() and recursion:

const flatten = (array) => array.flatMap(({ type, name, path, children }) => [
  { type, name, path },
  ...flatten(children || [])
]);

---

Complete snippet:

const data = [{
  type: "folder",
  name: "animals",
  path: "/animals",
  children: [{
    type: "folder",
    name: "cat",
    path: "/animals/cat",
    children: [{
      type: "folder",
      name: "images",
      path: "/animals/cat/images",
      children: [{
          type: "file",
          name: "cat001.jpg",
          path: "/animals/cat/images/cat001.jpg"
        }, {
          type: "file",
          name: "cat001.jpg",
          path: "/animals/cat/images/cat002.jpg"
        }
      ]
    }]
  }]
}];

const flatten = (array) => array.flatMap(({type, name, path, children}) => [
  { type, name, path },
  ...flatten(children || [])
]);

console.log(flatten(data));

Flat array to tree Javascript

This can be done with O(n) time complexity by leveraging object references. By creating a children array on each element and then adding the correct child to its parent's children array, you can accomplish building the whole tree.

const sqlData=[{id:1,label:"root",parentId:0},{id:2,label:"ant",parentId:1},{id:3,label:"cat",parentId:1},{id:4,label:"bear",parentId:3},{id:5,label:"dog",parentId:3},{id:6,label:"elephant",parentId:5},{id:7,label:"frog",parentId:1}];

const parentMap = {};
const root = [];

// Map parent positions
sqlData.forEach((el, i) => {
  parentMap[el.id] = i;
  el.children = [];
});

sqlData.forEach(({ id, parentId, label, children }) => {
  const insert = { [id]: { label, children } };
  if (parentId === 0) {
    root.push(insert);
    return;
  }
  sqlData[parentMap[parentId]].children.push(insert);
});

console.log(root);

---

Related Topics