Generating a tree structure using a JavaScript array

Question

Generating a tree structure using a JavaScript array

Looking to build a tree structure from a given list of data where the paths are represented like:

A-->B-->C-->D-->E..
A-->B-->C-->D-->F..
A-->F-->C-->D-->E..
.
.
.

All possible data paths are stored in an array. The desired output should look like:

Is there a way to achieve this using JavaScript? I am looking for a function called createTreeFunction :)

function parseData(data)
  {


   $.each(data, function (i, p) {
                   var arr = p.split("--->");

                 createTreeFunction(p);

                  });

   };
  function parseData(data)
      {


       $.each(data, function (i, p) {
                       var arr = p.split("--->");

                     createTreeFunction(p);

                      });

   };

javascript java tree

Answer 1

Answer №1

There are two main structures that can be used for building a tree with children: one using an array (Solution A) and the other using an object (Solution B).

An advantage of using an array over an object is the ability to directly iterate over the children. With an object, you first need to retrieve the keys before iteration is possible.

On the other hand, if you already know a child, accessing it through the key is faster. This also applies when inserting new nodes into the tree.

When using a children array, a getChild function is needed to check if a child is present.

_{Note: The provided data does not ensure the uniqueness of identifiers.}

Solution A with arrays for children:

function Node(id) {
    this.id = id;
    this.children = []; // array
}

Node.prototype.getChild = function (id) {
    var node;
    this.children.some(function (n) {
        if (n.id === id) {
            node = n;
            return true;
        }
    });
    return node;
};

var path = ['A-->B-->C-->D-->E', 'A-->B-->C-->D-->F', 'A-->F-->C-->D-->E'],
    tree = new Node('root');

path.forEach(function (a) {
    var parts = a.split('-->');
    parts.reduce(function (r, b) {
        var node = r.getChild(b);
        if (!node) {
            node = new Node(b);
            r.children.push(node);
        }
        return node;
    }, tree);
});

document.getElementById('out').innerHTML = JSON.stringify(tree, 0, 4);

<pre id="out"></pre>

Solution B with objects for children:

function Node(id) {
    this.id = id;
    this.children = {}; // object
}

var path = ['A-->B-->C-->D-->E', 'A-->B-->C-->D-->F', 'A-->F-->C-->D-->E'],
    tree = new Node('root');

path.forEach(function (a) {
    var parts = a.split('-->');
    parts.reduce(function (r, b) {
        if (!r.children[b]) {
            r.children[b] = new Node(b);
        }
        return r.children[b];
    }, tree);
});

document.getElementById('out').innerHTML = JSON.stringify(tree, 0, 4);

<pre id="out"></pre>

Both solutions utilize Array#forEach and Array#reduce for iterating through the given strings and returning the reference to the actual id. In case an id is not found, a new instance of the node is created and added to the array or object. The reference is then returned for the next id check.

Answer 2

There are two main structures that can be used for building a tree with children: one using an array (Solution A) and the other using an object (Solution B).

An advantage of using an array over an object is the ability to directly iterate over the children. With an object, you first need to retrieve the keys before iteration is possible.

On the other hand, if you already know a child, accessing it through the key is faster. This also applies when inserting new nodes into the tree.

When using a children array, a getChild function is needed to check if a child is present.

_{Note: The provided data does not ensure the uniqueness of identifiers.}

Solution A with arrays for children:

function Node(id) {
    this.id = id;
    this.children = []; // array
}

Node.prototype.getChild = function (id) {
    var node;
    this.children.some(function (n) {
        if (n.id === id) {
            node = n;
            return true;
        }
    });
    return node;
};

var path = ['A-->B-->C-->D-->E', 'A-->B-->C-->D-->F', 'A-->F-->C-->D-->E'],
    tree = new Node('root');

path.forEach(function (a) {
    var parts = a.split('-->');
    parts.reduce(function (r, b) {
        var node = r.getChild(b);
        if (!node) {
            node = new Node(b);
            r.children.push(node);
        }
        return node;
    }, tree);
});

document.getElementById('out').innerHTML = JSON.stringify(tree, 0, 4);

<pre id="out"></pre>

Solution B with objects for children:

function Node(id) {
    this.id = id;
    this.children = {}; // object
}

var path = ['A-->B-->C-->D-->E', 'A-->B-->C-->D-->F', 'A-->F-->C-->D-->E'],
    tree = new Node('root');

path.forEach(function (a) {
    var parts = a.split('-->');
    parts.reduce(function (r, b) {
        if (!r.children[b]) {
            r.children[b] = new Node(b);
        }
        return r.children[b];
    }, tree);
});

document.getElementById('out').innerHTML = JSON.stringify(tree, 0, 4);

<pre id="out"></pre>

Both solutions utilize Array#forEach and Array#reduce for iterating through the given strings and returning the reference to the actual id. In case an id is not found, a new instance of the node is created and added to the array or object. The reference is then returned for the next id check.

Answer 3

Answer №2

Two highly effective Object methods that I have developed for such scenarios are

Object.prototype.getNestedValue()

and

Object.prototype.setNestedValue()

. With the use of these functions, handling this task becomes as simple as a single line of JavaScript code.

Object.prototype.getNestedValue = function(...a) {
  return a.length > 1 ? (this[a[0]] !== void 0 && this[a[0]].getNestedValue(...a.slice(1))) : this[a[0]];
};
Object.prototype.setNestedValue = function(...a) {
  return a.length > 2 ? typeof this[a[0]] === "object" && this[a[0]] !== null ? this[a[0]].setNestedValue(...a.slice(1))
                                                                              : (this[a[0]] = typeof a[1] === "string" ? {} : new Array(a[1]),
                                                                                 this[a[0]].setNestedValue(...a.slice(1)))
                      : this[a[0]] = a[1];
};

var data = "A-->B-->C-->D-->E\nA-->B-->C-->D-->F\nA-->F-->C-->D-->E",
  datarr = data.split("\n").map(e => e.split("-->")), // get your list in an array
       o = {};
datarr.forEach(a => !o.getNestedValue(...a) && o.setNestedValue(...a,null));

console.log(JSON.stringify(o,null,2));

Answer 4

Two highly effective Object methods that I have developed for such scenarios are

Object.prototype.getNestedValue()

and

Object.prototype.setNestedValue()

. With the use of these functions, handling this task becomes as simple as a single line of JavaScript code.

Object.prototype.getNestedValue = function(...a) {
  return a.length > 1 ? (this[a[0]] !== void 0 && this[a[0]].getNestedValue(...a.slice(1))) : this[a[0]];
};
Object.prototype.setNestedValue = function(...a) {
  return a.length > 2 ? typeof this[a[0]] === "object" && this[a[0]] !== null ? this[a[0]].setNestedValue(...a.slice(1))
                                                                              : (this[a[0]] = typeof a[1] === "string" ? {} : new Array(a[1]),
                                                                                 this[a[0]].setNestedValue(...a.slice(1)))
                      : this[a[0]] = a[1];
};

var data = "A-->B-->C-->D-->E\nA-->B-->C-->D-->F\nA-->F-->C-->D-->E",
  datarr = data.split("\n").map(e => e.split("-->")), // get your list in an array
       o = {};
datarr.forEach(a => !o.getNestedValue(...a) && o.setNestedValue(...a,null));

console.log(JSON.stringify(o,null,2));

Generating a tree structure using a JavaScript array

Answer №1

Answer №2

Similar questions

Having issues with retrieving data using findOne or findById in Express and Node JS, receiving undefined values

Step-by-step guide on eliminating the modal post-validation

Experiencing issues with applying bootstrap style to pagination when using react-js-pagination

the order of initialization in angularjs directives with templateUrl

Using Node.js to dissect a nested JSON array into individual JSON objects

The time in Europe/Moscow timezone is exactly one hour ahead of the original date

Tips for applying multiple style properties to an element using JavaScript

Utilize a JSON file to generate a network visualization using the vis.js library

Is it possible to continuously re-render a React Functional Component with Axios and useState/useEffect?

Cross-Origin Resource Sharing (CORS) issue: The Access-Control-Allow-Headers in preflight response does not allow the Authorization request header field

Utilizing React and Material-UI to create an autocomplete feature for words within sentences that are not the first word

React Table Pagination Bug with Material UI Library

Center-align the text in mui's textfield

The placeholder of a select component within a wrapper component remains the same, even though the value may change

Can you retrieve a reference/pointer to a specific property of an object in JavaScript?

Tips for executing a callback function when triggering a "click" event in jQuery?

Node.js is receiving an empty body from Postman when using form-data in the request

Using jest in typescript to simulate HttpRequest body and InvocationContext in @azure/functions

What steps can I take to correct my code so that it only shows a single table?

Toggle the class of a div when clicked and then change the class of another div