Convert nested array of values to a tree structure

Question

I have a nested array that represents a parent child relationship, that I need to convert to a tree structure.

Example nested array

list = [
        ['lvl-1 item-1', 'lvl-2 item-1'],
        ['lvl-1 item-1', 'lvl-2 item-1', 'lvl-3 item-1'],
        ['lvl-1 item-1', 'lvl-2 item-1', 'lvl-3 item-2'],
        ['lvl-1 item-2', 'lvl-2 item-1', 'lvl-3 item-1'],
        ['lvl-1 item-2', 'lvl-2 item-2', 'lvl-3 item-2', 'lvl-4 item-1'],
    ]

Each tree node has the following structure.

{
    name: "item",
    parent: "parent_name",
    children: []
}

Each item in the nested array represents a level in the object.

Expected JSON

{
  "name": "0",
  "parent": null,
  "children": [
    {
      "name": "lvl-1 item-1",
      "parent": "0",
      "children": [
        {
          "name": "lvl-2 item-1",
          "parent": "lvl-1 item-1",
          "children": [
            {
              "name": "lvl-3 item-1",
              "parent": "lvl-2 item-1",
              "children": []
            },
            {
              "name": "lvl-3 item-2",
              "parent": "lvl-2 item-1",
              "children": []
            }
          ]
        }
      ]
    },
    {
      "name": "lvl-1 item-2",
      "parent": "0",
      "children": [
        {
          "name": "lvl-2 item-1",
          "parent": "lvl-1 item-2",
          "children": [
            {
              "name": "lvl-3 item-1",
              "parent": "lvl-2 item-1",
              "children": []
            }
          ]
        },
        {
          "name": "lvl-2 item-2",
          "parent": "lvl-1 item-2",
          "children": [
            {
              "name": "lvl-3 item-2",
              "parent": "lvl-2 item-2",
              "children": [
                {
                  "name": "lvl-4 item-1",
                  "parent": "lvl-3 item-2",
                  "children": []
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

The code below is what I came up with, but there is a lot of room for improvement.

First I loop each item in the list and all of its children.

I add each level name to a parent array so I can navigate it later to find existing child objects. Once I hit the end of the child loop I add the current level to the parent for use on the next iteration.

Once I've reached the end of the parents for loop I check if the current name exists in the children and add it if not.

This was produced with a lot of trial and error, I'm struggling to explain it accurately.

Can someone help me to review this code, to better understand it and improve it.

I had trouble getting the initial structure to work, I ended up creating what I believe is a redundant object with a children field so that it matched the expected format.

Any help will be much appreciated. If there is anything I haven't explained clearly please let me know.

list = [
    ['lvl-1 item-1', 'lvl-2 item-1'],
    ['lvl-1 item-1', 'lvl-2 item-1', 'lvl-3 item-1'],
    ['lvl-1 item-1', 'lvl-2 item-1', 'lvl-3 item-2'],
    ['lvl-1 item-2', 'lvl-2 item-1', 'lvl-3 item-1'],
    ['lvl-1 item-2', 'lvl-2 item-2', 'lvl-3 item-2', 'lvl-4 item-1'],
];

console.log(nestedArrayToJson(list));

function nestedArrayToJson(structure) {
    const top_item = '0';

    let data = {
        children: [
            {
                name: top_item,
                parent: null,
                children: [],
            }],
    };

    for(let i = 0; i < structure.length; i++) {
        let parents = [top_item];
        for(let j = 0; j < structure[i].length; j++) {
            let obj = data;
            for(parent of parents) {
                obj = obj.children.find(o => o.name === parent);
            }
            const name = structure[i][j];
            if(!obj.children.find(o => o.name === name)) {
                obj.children.push({
                    name,
                    parent,
                    children: [],
                });
            }
            parents.push(structure[i][j]);
        }
    }

    return data.children[0];
}

Updated Script

list = [
  ['lvl-1 item-1', 'lvl-2 item-1'],
  ['lvl-1 item-1', 'lvl-2 item-1', 'lvl-3 item-1'],
  ['lvl-1 item-1', 'lvl-2 item-1', 'lvl-3 item-2'],
  ['lvl-1 item-2', 'lvl-2 item-1', 'lvl-3 item-1'],
  ['lvl-1 item-2', 'lvl-2 item-2', 'lvl-3 item-2', 'lvl-4 item-1']
]

function createTree(arr, topItem = "Top") {
  const node = (name, parent = null) => ({
    name,
    parent,
    children: []
  });
  const addNode = (parent, child) => {
    parent.children.push(child);

    return child;
  };
  const findNamedNode = (name, parent) => {
    for (const child of parent.children) {
      if (child.name === name) {
        return child
      }
      const found = findNamedNode(name, child);
      if (found) {
        return found
      }
    }
  };

  const top = node(topItem);
  let current;

  for (const children of arr) {
    current = top;
    for (const name of children) {
      const found = findNamedNode(name, current);
      current = found ? found : addNode(current, node(name, current.name));
    }
  }

  return top;
}

console.log(createTree(list, 'lvl-0 item-1'))

Answer 1

Vernacular

Naming is very important and it starts by using the correct terminology.

There is no such thing as a JSON object as you use the term. There are JSON strings and JSON files. There is also a JSON built-in Object. It provides an API to help convert between Objects and JSON strings

JavaScript uses Object to store data in the form of properties.

Objects can be converted to JSON string using JSON.stringify, or can be created from a JSON string using JSON.parse. Not all object can be converted to JSON, while all valid JSON strings can be converted to an Object.

Your question title makes no sense...

"Convert nested array of values to a JSON object"

"JSON object" is more meaningfully as tree

"Convert nested array into a tree"

Style

• The variables data and parent should be declared as constants const as the references they hold do not change.
• The JavaScript naming convention is camelCase try to avoid using snake_case. Eg the name top_item should be topItem The only time that snake_case is used is for some types of constants, in which case we use use SNAKE_UPPER_CASE.
• When possible (you don't need the array index) use a for...of loop rather than a for(;;) loop

Code logic

Functions

Good code tries to avoid doing too much in one function. Breaking the code into distinct tasks and assigning those tasks to functions make it easier to manage as the complexity starts to grow.

You create the node object in two places. Good source code avoids repetition. The most conman way to avoid repetition is to create functions that do the same or similar things via a call.

You need to search the node to locate where to add new child nodes. The simplest way to search a tree is via a recursive function. Recursive functions exploit the similarity of nested data to reduce the complexity of the code.

Avoid redundancies

There is no need to create the data object as a top level parent. The child of data, data.children[0] can serve as the top parent.

Rewrite

We can rewrite the code breaking it into smaller functions.

There are 3 functions in the main one

1. node creates a new node
2. addNode adds a node to a parent node
3. findNamedNode will find a node with a name. If that node does not exist it returns undefined

The main body of the function just iterated each array, searching for each node by name. If one is found it moves to the next. If no node is found it creates and adds a new one.

function createTree(structure, topItem = "Top") {
    const node = (name, parent = null) => ({name, parent, children: []});
    const addNode = (parent, child) => (parent.children.push(child), child);
    const findNamedNode = (name, parent) => {
        for (const child of parent.children) {
            if (child.name === name) { return child }
            const found = findNamedNode(name, child);
            if (found) { return found }            
        }
    }
    const TOP_NAME = "Top";
    const top = node(TOP_NAME);
    var current;

    for (const children of structure) {
        current = top;
        for (const name of children) {
            const found = findNamedNode(name, current);
            current = found ? found : addNode(current, node(name, current.name));
        }
    }
    return top;
}

To make sure it all worked (no typos or idiotic coder intrusion) the snippet run it once on a simple data set.

logTree(createTree(data()));

function createTree(structure) {
    const node = (name, parent = null) => ({name, parent, children: []});
    const addNode = (parent, child) => (parent.children.push(child), child);
    const findNamed = (name, parent) => {
        for (const child of parent.children) {
            if (child.name === name) { return child }
            const found = findNamed(name, child);
            if (found) { return found }            
        }
    }
    const TOP_NAME = "Top", top = node(TOP_NAME);
    for (const children of structure) {
        let par = top;
        for (const name of children) {
            const found = findNamed(name, par);
            par = found ? found : addNode(par, node(name, par.name));
        }
    }
    return top;
}



















   function data() { return [['A1', 'B1'],['A1', 'B1', 'C1'],['A1', 'B1', 'C2'],['A2', 'B1', 'C1'],['A2', 'B2', 'C2', 'D1'],['A2', 'B2', 'C2', 'D2'],['A2', 'B2', 'C2', 'D3'],['A2', 'B2', 'C2', 'D4'],['A2', 'B2', 'C2', 'D5'],['A2', 'B3', 'C1', 'D1'],['A3', 'B1', 'C1', 'D1'],['A3', 'B1', 'C1', 'D2'], ['A3', 'B1', 'C1', 'D3']]; }





/*=============================================================================*/
// Support code unrelated to answer
function log(textContent) {
    info.appendChild(Object.assign(document.createElement("div"),{textContent}));
}    
function logTree(parent, indent = "", end) {
    const tail = parent.children.length > 0 ? "┬" : "─";
    if(end){
        log(indent + "└──┬─" + "►parent: " + parent.parent);
        log(indent + "   └" + tail + "►name..: " + parent.name);
        indent +="    ";
    } else {
        log(indent + "├──┬─" + "►parent: " + parent.parent);
        log(indent + "│  └" + tail + "►name..: " + parent.name);
        indent +="│   ";
    }
    var idx = 0;
    for (const child of parent.children) {
        logTree(child, indent, (idx++ === parent.children.length -1));
    }
}

body {background:black}
#info {color:#CC0;font-size:smaller;white-space:pre-wrap;}

<code id="info"></code>