Question 202880 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – How can I build an array of the parent IDs of each element including its ID?

I would like to get the hierarchy of every single element of the array

I have this object array

[
    {
        "id": "1",
        "name": "Car",
        "parentId": "0",
        "parents": []
    },
    {
        "id": "2",
        "name": "Car > Steering wheel",
        "parentId": "1",
        "parents": []
    },
    {
        "id": "3",
        "name": "Car > Wheel",
        "parentId": "1",
        "parents": []
    },
    {
        "id": "4",
        "name": "Car > Wheel > Wheel rim",
        "parentId": "3",
        "parents": []
    },
    {
        "id": "5",
        "name": "Bus",
        "parentId": "0",
        "parents": []
    },
      {
        "id": "6",
        "name": "Bus > Wheel",
        "parentId": "5",
        "parents": []
    }
]

The result I need to get is the following array with the ‘parents’ key set

[
    {
        "id": "1",
        "name": "Car",
        "parentId": "0",
        "parents": ["1"]
    },
    {
        "id": "2",
        "name": "Car > Steering wheel",
        "parentId": "1",
        "parents": ["1","2"]
    },
    {
        "id": "3",
        "name": "Car > Wheel",
        "parentId": "1",
        "parents": ["1","3"]
    },
    {
        "id": "4",
        "name": "Car > Wheel > Wheel rim",
        "parentId": "3",
        "parents": ["1","3","4"]
    },
    {
        "id": "5",
        "name": "Bus",
        "parentId": "0",
        "parents": ["5"]
    },
      {
        "id": "6",
        "name": "Bus > Wheel",
        "parentId": "5",
        "parents": ["5","6"]
    }
]

As you can see, ‘parents’ contains its ID and its parents IDs.

I tried with map but failed. What do you suggest I do?

I tried this but I know it’s not good

   let arr = [];
   for (let i = 0; i < flattenArray.length; i++) {
     let node = flattenArray[i];
     let id = node.id;
     let parentId = node.parentId;
     if (parentId != "0") {
       node.parents = [id, parentId];
       arr.push(node);
     } else {
       node.parents = [id];
       arr.push(node);
     }
   }
Tags:

2

Answers


  1. 0

    There are a couple things that need to be done.

    1. Build a map of parent to children IDs
    2. Gather the parents by recursively mapping child IDs
    3. (Optionally) Gather child IDs
    const data = [
  { "id": "1", "name": "Car",                     "parentId": "0", "parents": [] },
  { "id": "2", "name": "Car > Steering wheel",    "parentId": "1", "parents": [] },
  { "id": "3", "name": "Car > Wheel",             "parentId": "1", "parents": [] },
  { "id": "4", "name": "Car > Wheel > Wheel rim", "parentId": "3", "parents": [] },
  { "id": "5", "name": "Bus",                     "parentId": "0", "parents": [] },
  { "id": "6", "name": "Bus > Wheel",             "parentId": "5", "parents": [] }
];


const main = () => {
  updateData(data);
  console.log(data);
};

const updateData = (data) => {
  const idTree = buildIdTree(data);
  for (let item of data) {
    item.parents = gatherParents(idTree, item.id);
    item.children = gatherChildren(idTree, item.id);
  }
};

const buildIdTree = (data) => {
  const parentChildMap = buildParentChildMap(data);
  const root = { id: '0', children: [] };
  populateTree(root, parentChildMap);
  return root;
};

const buildParentChildMap = (data) => {
  const parentChildMap = new Map();
  for (let item of data) {
    const parentIds = parentChildMap.get(item.parentId) ?? new Set();
    parentIds.add(item.id);
    parentChildMap.set(item.parentId, parentIds);
  }
  return parentChildMap;
}

const populateTree = (node, parentChildMap) => {
  if (!node) return;
  const childIds = parentChildMap.get(node.id);
  if (!childIds) return;
  for (let childId of childIds) {
    const child = { id: childId, children: [] };
    node.children.push(child);
    populateTree(child, parentChildMap);
  }
};

const gatherParents = (node, id) =>
  [...new Set([ node.id, ...node.children
      .map(child => gatherParents(child, id))
      .find(ids => ids.includes(id)) ?? []
  ].filter(id => id !== '0'))].sort();

const gatherChildren = (tree, id) => {
  const node = searchTree(tree, id), ids = [];
  collectIds(node, ids);
  return ids;
};

const collectIds = (node, ids) => {
  if (!node) return;
  for (let child of node.children) {
    ids.push(child.id);
    collectIds(child, ids);
  }
};

const searchTree = (node, id) => {
  if (!node) return null;
  if (node.id == id) return node;
  if (node.children == null) return null;
  let result = null;
  for (let i = 0; result == null && i < node.children.length; i++) {
    result = searchTree(node.children[i], id);
  }
  return result;
}

main();
    .as-console-wrapper { top: 0; max-height: 100% !important; }
    Login or Signup to reply.
  2. 0
    • Map your items into an object by ID
    • Walk this map for each item to get its path in the tree:
    const data = [
    { "id": "1", "name": "Car", "parentId": "0", "parents": [] },
    { "id": "2", "name": "Car > Steering wheel", "parentId": "1", "parents": [] },
    { "id": "3", "name": "Car > Wheel", "parentId": "1", "parents": [] },
    { "id": "4", "name": "Car > Wheel > Wheel rim", "parentId": "3", "parents": [] },
    { "id": "5", "name": "Bus", "parentId": "0", "parents": [] },
    { "id": "6", "name": "Bus > Wheel", "parentId": "5", "parents": [] },
];

const map = {};

for (const item of data) {
    map[item.id] = item;
}

for (const item of data) {

    let parent = item;
    do {
        item.parents.unshift(parent.id);
    } while (parent = map[parent.parentId]);

}

console.log(data);
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search