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

Checking the existence of a user's email in Node.js

Rely on the razor method for generating URLs

Is it possible to manipulate a modal within a controller by utilizing a certain attribute in HTML, based on specific conditions (without relying on any bootstrap services), using AngularJS?

The AWS Lambda function in Node.js encountered an internal server error

Parsing JSON data in Android received from a .NET web service

What is the best way to gather user input and incorporate it into a selected template, ensuring it is verified before sending?

Utilizing AJAX in Wordpress to Dynamically Update HREF Links

javascript create smooth transitions when navigating between different pages

Assign the values from the axios response to variables within the exported const

Painting Magic: Exploring the World of Canvas Zoom and Moves

The URL overwrites the Ajax transfer type

Overriding a shared module service in Angular from a separate module: A step-by-step guide

Amazon S3 Landing Page Featuring Contact Form

Send a JavaScript variable to Twig

How can I efficiently remove elements from the end of an array in Vue.js?

Convert a two-column layout on the web into a single-column layout for mobile devices, featuring dynamic

Is it more beneficial to keep a function inside or outside another function if it is only being used within it?

Create a simple carousel using only vanilla JavaScript, without relying on any external plugins

Utilizing HTML injection to access both the Chrome API and global variables

Achiever.js - Incorporating incremental progress with half stars instead of whole stars