Creating a hierarchical tree from a one-dimensional array

I have an array of objects with a "lv" property, which is always an integer greater than or equal to 0.

[
  {lv: 0, name: "A"},
  {lv: 1, name: "B"},
  {lv: 1, name: "C"},
  {lv: 2, name: "D"},
  {lv: 3, name: "E"},
  {lv: 1, name: "F"},
  {lv: 0, name: "G"},
]

This data was exported from legacy software and represents a hierarchical tree structure. The "lv" property indicates the depth of each node in the tree relative to its parent node in the array. For instance, A is at level 0 (root); B is at level 1, making it a child of A; C is also level 1, making it a sibling of B and a child of A; and so on. This creates the following structure:

├ A
│ ├ B
│ ├ C
│ │ └ D
│ │   └ E
│ └ F
└ G

I am trying to write a function that can transform this flat array into a nested structure that better reflects the tree, like this:

[
  {
    name: "A",
    children: [
      {
        name: "B",
        children: null
      },
      {
        name: "C",
        children: [
          {
            name: "D",
            children: [
              {
                name: "E",
                children: null
              }
            ]
          }
        ]
      },
      {
        name: "F",
        children: null
      }
    ]
  },
  {
    name: "G",
    children: null
  }
]

In this structure, each node has an array of children under the "children" property, structured recursively.

I attempted to create a recursive function for this purpose, but it fails when encountering a node that moves up the tree (e.g., a level 1 node coming after a level 3 node). Here is the function I wrote:

function buildTree(arr) {
  let siblings = [], children = null

  while (arr.length) {
    let node = arr.shift()

    if (arr.length) {
      let nodeLv = +node.lv
      let nextNodeLv = +arr[0].lv
      if (nextNodeLv > nodeLv) {
        children = buildTree(arr)
      }
    }

    let newNode = {
      name: node.name,
      children: children
    }

    siblings.push(newNode)
  }

  return siblings
}

However, instead of the desired structure, the function produces the following:

└ A
  ├ B
  └ C
    └ D
      └ E
        └ F
          └ G

It seems to work correctly when building deeper levels, but struggles to handle backwards movements (like going from E to F or F to G).

What am I missing here? Is there a better approach to solving this problem?

Answer №1

To avoid using a stack or recursion, simply keep track of the last items in each level to assign children to them:

const arr = [
  {lv: 0, name: "A"},
  {lv: 1, name: "B"},
  {lv: 1, name: "C"},
  {lv: 2, name: "D"},
  {lv: 3, name: "E"},
  {lv: 1, name: "F"},
  {lv: 0, name: "G"},
]
const result = [], last = [{children: result}]; // storing the last nodes of levels
for(const {lv, name} of arr){
  const node = {name, children: null};
  (last[lv].children ??= []).push(node);
  last[lv + 1] = node;
}

console.log(result);
.as-console-wrapper{max-height:100%!important};

Also, here is a performance comparison:

` Chrome/125
--------------------------------------------------------------------------------------
>                 n=7       |       n=70        |       n=700       |      n=7000     
Alexander   ■ 1.00x x1m 111 | ■ 1.00x x100k  84 | ■ 1.00x x100k 858 | ■ 1.00x x10k 942
trincot       1.14x x1m 127 |   1.11x x100k  93 |   1.13x  x10k  97 |   1.16x  x1k 109
Andrew        6.20x x1m 688 |   5.82x x100k 489 |   5.26x  x10k 451 |   5.98x  x1k 563
-------------------------------------------------------------------------------------- `

Open in the playground

const $chunk = [
  {lv: 0, name: "A"},
  {lv: 1, name: "B"},
  {lv: 1, name: "C"},
  {lv: 2, name: "D"},
  {lv: 3, name: "E"},
  {lv: 1, name: "F"},
  {lv: 0, name: "G"},
]

const $input = [], arr = $input, data = $input;

// @benchmark Alexander
const result = [], last = [{children: result}]; // storing the last nodes of levels
for(const {lv, name} of arr){
  const node = {name, children: null};
  (last[lv].children ??= []).push(node);
  last[lv + 1] = node;
}
result;

// @benchmark trincot
function makeHierarchy(flat) {
    const hierarchy = [];
    const stack = [{children: hierarchy}];
    for (const {lv, name} of flat) {
        while (lv < stack.length - 1) stack.pop();
        const obj = {name, children: null};
        (stack.at(-1).children ??= []).push(obj);
        stack.push(obj);
    }
    return hierarchy;
}

makeHierarchy(arr);

// @benchmark Andrew
{
// assigning a parent to each item
data.forEach((e, i, r) => {
  let last = r[i-1];
  if(last) {
    e.parent = last;
    for(let j=(last.lv - e.lv)+1; j--;) e.parent = e.parent.parent;
  }
})

// the result will directly contain the items with no parent
let result = data.filter(e => !e.parent);

// adding each item to a children array created for its parent
data.filter(e => e.parent).forEach(e => (e.parent.children ??= []).push(e))

// removing unnecessary properties
data.forEach(e => {
  delete e.parent
  delete e.lv
  if(!e.children?.length) e.children = null
})
result;
}

/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));

Answer №2

To create a hierarchy, utilize a stack where each state represents the current path at the level with node instances. Add the current node to the parent's list of children at the top of the stack. Remove nodes from the stack as the level decreases.

function buildHierarchy(flatData) {
    const hierarchy = [];
    const stack = [{children: hierarchy}];
    for (const {level, name} of flatData) {
        while (level < stack.length - 1) stack.pop();
        const object = {name, children: []};
        stack.at(-1).children.push(object);
        stack.push(object);
    }
    return hierarchy;
}

// Example using data provided
const flatData = [{level: 0, name: "A"},{level: 1, name: "B"},{level: 1, name: "C"},{level: 2, name: "D"},{level: 3, name: "E"},{level: 1, name: "F"},{level: 0, name: "G"},];
const hierarchyTree = buildHierarchy(flatData);
console.log(hierarchyTree);

It is worth noting that in this setup, leaf nodes have their children property initialized as an empty array for consistency. This approach offers more coherence compared to having null values in those cases. If null values are required, consider utilizing the following variant:

function buildHierarchy(flatData) {
    const hierarchy = [];
    const stack = [{children: hierarchy}];
    for (const {level, name} of flatData) {
        while (level < stack.length - 1) stack.pop();
        const object = {name, children: null};
        (stack.at(-1).children ??= []).push(object);
        stack.push(object);
    }
    return hierarchy;
}

const flatData = [{level: 0, name: "A"},{level: 1, name: "B"},{level: 1, name: "C"},{level: 2, name: "D"},{level: 3, name: "E"},{level: 1, name: "F"},{level: 0, name: "G"},];
const hierarchyTree = buildHierarchy(flatData);
console.log(hierarchyTree);

Answer №3

Implementing this process without using recursion is entirely possible. By first identifying the correct parent for each item and then organizing them accordingly within the hierarchy, the task can be accomplished efficiently.

const elements = [{"lv":0,"name":"X"},{"lv":1,"name":"Y"},{"lv":1,"name":"Z"},{"lv":2,"name":"W"},{"lv":3,"name":"V"},{"lv":1,"name":"U"},{"lv":0,"name":"T"}]

// assign a suitable parent to each element
elements.forEach((element, index, array) => {
  let previous = array[index-1];
  if(previous) {
    element.parent = previous;
    for(let count=(previous.lv - element.lv)+1; count--;) element.parent = element.parent.parent;
  }
})

// gather items that have no parent directly in the result
let resultingElements = elements.filter(element => !element.parent);

// group each element under its designated parent's children array
elements.filter(element => element.parent).forEach(element => (element.parent.children ??= []).push(element))

// remove unnecessary properties from the elements
elements.forEach(element => {
  delete element.parent
  delete element.lv
  if(!element.children?.length) element.children = null
})

console.log(resultingElements)

Similar questions

If you have not found the answer to your question or you are interested in this topic, then look at other similar questions below or use the search

Personalize the menu item in material ui

Currently, I have a <select> component from Material UI and I am iterating over the menuItem elements. Here is a sample you can reference: here My issue lies in trying to change the background color of each menu item. Although I attempted to do so, ...

Add an item to one ng-repeat by clicking a button in another ng-repeat

I'm trying to manipulate two ng-repeats by adding values from one to the other and vice versa. Here's a snippet of my HTML: <div id="external-events"> <div ng-repeat="selected in selectedcolumn"> <div class="external-event b ...

Utilize Node.js to gather information from various websites

I want to create a program that can download data from various websites like WHO, UNICEF, Eurostat, etc. and then convert this data into JSON format. This process is known as web scraping, right? The data may be in different formats such as html, PDF, xls ...

What is the process for specifying a datatype in a MySQL column that is used to store an array?

I'm currently Java programming and facing a challenge with an input dialog setting attributes in columns. One of the columns is named "Notes" and it needs to receive an array. Here are my current columns: Name: (patient's name), [varchar]. CPF: ...

Can a Vue component in SFC form be utilized as a mixin?

Consider this scenario, where I have a component created in SFC format: // Parent.vue <template> <div> {{ txt }} </div> </template> <script> export default { name: 'ParentComponent', data() { return ...

Determine in Node.js whether an image is empty or not

I am in the process of developing a testing application that generates an image based on the URL provided by the user. The screenshots are captured using phantomJS and nightmareJS. Occasionally, users may input a non-existent URL, resulting in a blank ima ...

Tips on making a bubble similar to the one on the Google homepage that prompts you to make Google your default homepage

I am looking for a subtle way to suggest visitors to make my website their homepage. While I considered using a popup, I didn't want it to be too intrusive for the visitor to see a large popup every time they visited the website. I'm interested ...

An error is thrown when trying to retrieve Objects: Uncaught TypeError - Object function ParsePromise()

By obtaining a Document object with its id, the following code proceeds to locate corresponding sections based on the object. The document identifies a Parse object and document.toJSON converts this into a Javascript object. Furthermore, sections represent ...

Tips for alternating the color of <li> or <tr> elements consecutively

Looking to alternate the background color of li or tr elements consecutively. Please note: A static class will not work as I need to call this in a while loop. The desired output should look like: <li>line1</li> //white background <li> ...

Tips for preventing duplicate triggering of a broadcast event from app.js in AngularJS

Within the app.js file, I am utilizing a callback function that broadcasts on the $rootScope to trigger a method in the second controller. function onSuccess(state) { if (state != true) { } else { $rootScope.$broadcast(&a ...

Using Redux and Typescript with functional components: the imported component depends on props provided by Redux

I'm currently working on a component that has the following structure: It features an interface with a "alerts" property It's connected to Redux and receives the "alerts" from props ...

How can I showcase Google images on my website?

I'm currently working on a project where I want to showcase images on my website retrieved from Google Images based on a keyword stored in an array. Here's the code I have so far: <?php $lines = file('things.txt'); echo $lines[arra ...

Determining the spatial location of an object in Three.js in relation to the camera for the purpose of creating a trail

In my scene, I have an object (a pen) that rotates around its axis in the render loop using the following code: groupPen.rotation.y += speed; groupPen.rotation.x += speed; Additionally, I have a TrackballControls that allows the user to rotate the entire ...

Ways to create a class method to increase a counter?

Can someone help me figure out how to create a custom function or class from the code below? I want to be able to import this module in order to easily increment a count whenever an event occurs in my application. I'm tired of having to manually inpu ...

Is there a way to dynamically apply the "active" class to a Vue component when it is clicked?

Here is the structure of my Vue component: Vue.component('list-category', { template: "#lc", props: ['data', 'category', 'search'], data() { return { open: false, categoryId: this.category ...

store the array in a separate class apart from the main method or class

I am encountering an error message that indicates the need for braces after the array declaration. I am unsure about how to proceed. My intention is to create an array that is not located within my main method. The array should consist of instances of a ...

Navigating nested objects within an array: A guide to iterating through multiple layers of objects

After receiving a payload from Firebase, I found an array with 3 objects inside, each of which also contains additional objects. Here is the screenshot for reference: https://i.sstatic.net/kII6g.png When I console.log my 'months' array, this i ...

Issues with displaying charts have been reported for generator-angular-fullstack and angular-chart.js

After working with Angular for some time, I decided to give Yeoman and generator-angular-fullstack a try. My main goal was to use angular-chart.js to display a chart in a particular view called poll.html. Surprisingly, everything loaded correctly except fo ...

Troubleshooting Problems with Owl Carousel Loading

Having trouble with Owl Carousel loading issue. I've set up my carousel using the Owl Carousel jQuery plugin as guided, but it's showing me an "owl-carousel loading" class added to the DOM (owl-loading). I've tried adding custom styles and J ...

Adding a live video stream from an external website using HTML and JavaScript

I'm currently working on incorporating live video streams from another website into my own for added convenience, but I'm having trouble getting it to function properly. I have created a dropdown menu using select and options, with the select id= ...