What is the best way to programmatically organize a tree structure using an array containing parent-child configurations?

Question

What is the best way to programmatically organize a tree structure using an array containing parent-child configurations?

I am looking to restructure my JavaScript object into a hierarchical tree pattern object. Here is my current object:

let input = [
  {'id':1 ,'pid' : 0},
  {'id':2 ,'pid' : 1},
  {'id':3 ,'pid' : 2},
  {'id':4 ,'pid' : 2},
  {'id':5 ,'pid' : 3},
  {'id':6 ,'pid' : 3},
  {'id':7 ,'pid' : 4},
  {'id':8 ,'pid' : 4},
  {'id':9 ,'pid' : 4}
];

I came across this helpful snippet online, which works well (unfortunately, I forgot the source, but thank you anyway)

let input = [
{'id':1 ,'pid' : 0},
{'id':2 ,'pid' : 1},
{'id':3 ,'pid' : 2},
{'id':4 ,'pid' : 2},
{'id':5 ,'pid' : 3},
{'id':6 ,'pid' : 3},
{'id':7 ,'pid' : 4},
{'id':8 ,'pid' : 4},
{'id':9 ,'pid' : 4}
];

let register = {};

let output = {};

for (let el of input) {
  el = Object.assign({}, el);
  register[el.id] = el;
 
  if (!el.pid) { 
    output[el.id] = el;
  } else { 
    register[el.pid][el.id] = el
  }

  delete el.pid;
  delete el.id
}

document.body.innerHTML = "<pre>" + (JSON.stringify(output, undefined, 2))

However, when I changed the PID value from {'id':4 ,'pid' : 2} to {'id':4 ,'pid' : 9}, an issue arose with register[el.pid] being undefined.

I need assistance in resolving this issue, thank you in advance.

javascript arrays object tree parent-child

Answer 1

Answer №1

It is impossible to move a parent to its own children, unless you are in a time travel scenario depicted in novels or movies.

If you want to create a tree structure without deleting any properties, you can achieve this by iterating through the data with a single loop, using the id and parent values to connect the nodes and generating an object with the root parent set as 0.

This method works even with unsorted data.

const
    input = [{ id: 1, pid: 0 }, { id: 2, pid: 1 }, { id: 3, pid: 2 }, { id: 4, pid: 2 }, { id: 5, pid: 3 }, { id: 6, pid: 3 }, { id: 7, pid: 4 }, { id: 8, pid: 4 }, { id: 9, pid: 4 }],
    tree = {};

for (const { id, pid } of input) {
    tree[pid] ??= {};
    tree[id] ??= {};
    tree[pid][id] ??= tree[id];
}

console.log(tree[0]);

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

Answer 2

It is impossible to move a parent to its own children, unless you are in a time travel scenario depicted in novels or movies.

If you want to create a tree structure without deleting any properties, you can achieve this by iterating through the data with a single loop, using the id and parent values to connect the nodes and generating an object with the root parent set as 0.

This method works even with unsorted data.

const
    input = [{ id: 1, pid: 0 }, { id: 2, pid: 1 }, { id: 3, pid: 2 }, { id: 4, pid: 2 }, { id: 5, pid: 3 }, { id: 6, pid: 3 }, { id: 7, pid: 4 }, { id: 8, pid: 4 }, { id: 9, pid: 4 }],
    tree = {};

for (const { id, pid } of input) {
    tree[pid] ??= {};
    tree[id] ??= {};
    tree[pid][id] ??= tree[id];
}

console.log(tree[0]);

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

Answer 3

Answer №2

It is feasible to programatically aggregate a tree from configuration items that define parent-child relationships, even if the items are not in perfect order, as long as the relationships are valid and representative.

Circular references between parent and child nodes, such as those created by changing { 'id': 4, 'pid': 2 } to { 'id': 4, 'pid': 9 }, break the connection within the overall tree structure that can be represented. These circular references are considered invalid, leading to the loss of any other valid substructures connected to them.

The validity of this statement is demonstrated through the example code provided below ...

function aggregateTree( 
  { index = {}, result = {} }, // accumulator.
  { id, pid },                 // parent child config.
) {
  const childItem = (index[id] ??= { [id]: {} });
  const parentItem = (pid !== 0)
    && (index[pid] ??= { [pid]: {} })
    || null;
  const node = (parentItem !== null)
    && parentItem[pid] // programmatically build partial trees.
    || result // assign partial tree references at root/resul level.

  Object.assign(node, childItem);

  return { index, result };
}

console.log('unordered but valid parent child relationships ...', [

  { 'id': 1 ,'pid': 0 },
  { 'id': 2 ,'pid': 1 },
  { 'id': 3 ,'pid': 2 },

  { 'id': 12, 'pid': 0 },

  { 'id': 11, 'pid': 6 },
  { 'id': 10, 'pid': 6 },

  { 'id': 4, 'pid': 5 },

  { 'id': 5 ,'pid': 3 },
  { 'id': 6 ,'pid': 3 },

  { 'id': 7 ,'pid': 4 },
  { 'id': 8 ,'pid': 4 },
  { 'id': 9 ,'pid': 4 }

].reduce(aggregateTree, { result: {} }).result);

console.log('ordered but partially invalid parent child relationships ...', [

  // circular references like 4 to 9 and 9 to 4,
  // thus not being linked to the overall tree,
  // can not be aggregated and displayed.

  { 'id': 1, 'pid': 0 },
  { 'id': 2, 'pid': 1 },
  { 'id': 3, 'pid': 2 },

  { 'id': 4, 'pid': 9 }, // circular thus disconnected.
  // { 'id': 9, 'pid': 4 },

  { 'id': 5, 'pid': 3 },
  { 'id': 6, 'pid': 3 },

  { 'id': 7, 'pid': 4 }, // lost due to being linked to a circular reference.
  { 'id': 8, 'pid': 4 }, // lost due to being linked to a circular reference.

  { 'id': 9, 'pid': 4 }, // circular thus disconnected.
  // { 'id': 4, 'pid': 9 },

].reduce(aggregateTree, { result: {} }).result);

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

Answer 4

It is feasible to programatically aggregate a tree from configuration items that define parent-child relationships, even if the items are not in perfect order, as long as the relationships are valid and representative.

Circular references between parent and child nodes, such as those created by changing { 'id': 4, 'pid': 2 } to { 'id': 4, 'pid': 9 }, break the connection within the overall tree structure that can be represented. These circular references are considered invalid, leading to the loss of any other valid substructures connected to them.

The validity of this statement is demonstrated through the example code provided below ...

function aggregateTree( 
  { index = {}, result = {} }, // accumulator.
  { id, pid },                 // parent child config.
) {
  const childItem = (index[id] ??= { [id]: {} });
  const parentItem = (pid !== 0)
    && (index[pid] ??= { [pid]: {} })
    || null;
  const node = (parentItem !== null)
    && parentItem[pid] // programmatically build partial trees.
    || result // assign partial tree references at root/resul level.

  Object.assign(node, childItem);

  return { index, result };
}

console.log('unordered but valid parent child relationships ...', [

  { 'id': 1 ,'pid': 0 },
  { 'id': 2 ,'pid': 1 },
  { 'id': 3 ,'pid': 2 },

  { 'id': 12, 'pid': 0 },

  { 'id': 11, 'pid': 6 },
  { 'id': 10, 'pid': 6 },

  { 'id': 4, 'pid': 5 },

  { 'id': 5 ,'pid': 3 },
  { 'id': 6 ,'pid': 3 },

  { 'id': 7 ,'pid': 4 },
  { 'id': 8 ,'pid': 4 },
  { 'id': 9 ,'pid': 4 }

].reduce(aggregateTree, { result: {} }).result);

console.log('ordered but partially invalid parent child relationships ...', [

  // circular references like 4 to 9 and 9 to 4,
  // thus not being linked to the overall tree,
  // can not be aggregated and displayed.

  { 'id': 1, 'pid': 0 },
  { 'id': 2, 'pid': 1 },
  { 'id': 3, 'pid': 2 },

  { 'id': 4, 'pid': 9 }, // circular thus disconnected.
  // { 'id': 9, 'pid': 4 },

  { 'id': 5, 'pid': 3 },
  { 'id': 6, 'pid': 3 },

  { 'id': 7, 'pid': 4 }, // lost due to being linked to a circular reference.
  { 'id': 8, 'pid': 4 }, // lost due to being linked to a circular reference.

  { 'id': 9, 'pid': 4 }, // circular thus disconnected.
  // { 'id': 4, 'pid': 9 },

].reduce(aggregateTree, { result: {} }).result);

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

What is the best way to programmatically organize a tree structure using an array containing parent-child configurations?

Answer №1

Answer №2

Similar questions

Troubleshooting Firebase functions that end with socket hang up error ECONNRESET

Responding to a tweet with the help of twit and Node.js

Harnessing WireframeHelper with Objects at the Ready

Is it possible to define an object as a property within a class in PHP?

The JSON object is coming back as null

Retrieving and storing information from a form without the need to submit it

Returning spliced elements will yield a nested array

nanoExpress Route Isolation

What is the method for setting focus on the next tab using AngularJS?

Utilizing a form on numerous occasions prior to its submission

Tips for transitioning frontend JS to Angular 2 for seamless integration with a PHP MVC backend system

Discover the method to calculate the combined file size of multiple uploads with jquery

Asynchronously loading images within a div that has overflow: scroll, as they come into view

Troubleshooting JavaScript: Dealing with JSON Import Issues Involving Arrays of Objects

Showing a section of a DIV inside an iframe

Managing the challenges of handling numerous AJAX post errors stemming from multiple form submissions

What Causes My Issue with $(document).ready()?

Determine if a cookie is set in Vue.js without requiring a page refresh

What is the best way to switch to a new HTML page without causing a page refresh or altering the URL?

Uploading images with AngularJS and PHP