How can I map this array to a tree of nested object?

Question

I am trying to create tree base on a flat array. My input does not have any kind of parent id. Each element use a id which is a kind of path with this format ancestor(n+1)-ancestor1-Grandparent-parent-id etc.

For example when input is

[{"id":"1","children":[]},{"id":"1-1"}]

then output should be

[{"id":"1","children":[{"id":"1-1"}]}]

and given

[
  {
    "id": "1",
    "children": []
  },
  {
    "id": "1-1",
    "children": []
  },
  {
    "id": "1-1-1"
  },
  {
    "id": "1-2"
  },
  {
    "id": "2",
    "children": []
  },
  {
    "id": "2-1"
  }
]

then

[{
    "id": "1",
    "children": [
      {
        "id": "1-1",
        "children": [
          {
            "id": "1-1-1"
          }
        ]
      },
      {
        "id": "1-2"
      }
    ]
  },
  {
    "id": "2",
    "children": [
      {
        "id": "2-1"
      }
    ]
  }
]

My current code:

let list = [{
    "name": "Europe",
    "employeeCount": 1,
    "children": [],
    "id": "1"
  },
  {
    "name": "France",
    "employeeCount": 1,
    "children": [],
    "id": "1-1"
  },
  {
    "name": "Paris",
    "employeeCount": 1,
    "children": [],
    "id": "1-1-1"
  },
  {
    "name": "Foo Bar",
    "isInactive": false,
    "id": "1-1-1-27"
  }
]

// I try this but I am not sure how to loop...
function buildTree(list) {
  let tree = []
  for (var i = 0; i < list.length; i++) {

    if (!list[i].id.includes('-')) {
      tree.push(list[i]);
    } else {
      tree[tree.length - 1].children.push(list[i]);
    }
  }
  return tree;
}


let tree = buildTree(list)

console.log(tree[0].children[0].children[0] === "Paris")

Related to: How to efficiently build a tree from a flat structure?

score 0 · Accepted Answer · answered Oct 22 '18 at 08:00

Since your array is sorted, you can achieve it with a recursive function:

const delimiter = '-';
const delimiterCount = x => x.id.split('').reduce((acc, c) => acc + (c === delimiter), 0);


function descend(tree, node, count) {
	if (count == 0) {
		tree.push(node);
		return;
	}

	return descend(tree[tree.length - 1].children, node, count - 1);
}

function buildTree(list){
	let tree = []
	for (var i = 0; i < list.length; i++) {
		let count = delimiterCount(list[i]);

		descend(tree, list[i], count);
	}
	return tree;
}

and some "raw" unit tests:

{
let actual = buildTree([{"id":"1","children":[]},{"id":"1-1","children":[]},{"id":"1-1-1","children":[]},{"id":"1-1-1-1","children":[]},{"id":"1-1-1-1-1"}])
let expected = [{"id":"1","children":[{"id":"1-1","children":[{"id":"1-1-1","children":[{"id":"1-1-1-1","children":[{"id":"1-1-1-1-1"}]}]}]}]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) {console.log("expected:\n" + JSON.stringify(expected, null, 2));console.log("actual:\n" + JSON.stringify(actual, null, 2))}
else console.log(true);
}
{
let actual = buildTree([{"id":"1","children":[]},{"id":"1-1","children":[]},{"id":"1-1-1","children":[]},{"id":"1-1-1-1"}])
let expected = [{"id":"1","children":[{"id":"1-1","children":[{"id":"1-1-1","children":[{"id":"1-1-1-1"}]}]}]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) {console.log("expected:\n" + JSON.stringify(expected, null, 2));console.log("actual:\n" + JSON.stringify(actual, null, 2))}
else console.log(true);
}
{
let actual = buildTree([{"id":"1","children":[]},{"id":"1-1","children":[]},{"id":"1-1-1"},{"id":"1-2","children":[]},{"id":"1-2-1"},{"id":"2","children":[]},{"id":"2-1"}])
let expected = [{"id":"1","children":[{"id":"1-1","children":[{"id":"1-1-1"}]},{"id":"1-2","children":[{"id":"1-2-1"}]}]},{"id":"2","children":[{"id":"2-1"}]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) {console.log("expected:\n" + JSON.stringify(expected, null, 2));console.log("actual:\n" + JSON.stringify(actual, null, 2))}
else console.log(true);
}
{
let actual = buildTree([{"id":"1","children":[]},{"id":"1-1","children":[]},{"id":"1-1-1"},{"id":"1-2"},{"id":"2","children":[]},{"id":"2-1"}])
let expected = [{"id":"1","children":[{"id":"1-1","children":[{"id":"1-1-1"}]},{"id":"1-2"}]},{"id":"2","children":[{"id":"2-1"}]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) {console.log("expected:\n" + JSON.stringify(expected, null, 2));console.log("actual:\n" + JSON.stringify(actual, null, 2))}
else console.log(true);
}
{
let actual = buildTree([{"id":"1","children":[]},{"id":"1-1","children":[]},{"id":"1-1-1"},{"id":"2","children":[]},{"id":"2-1"}])
let expected = [{"id":"1","children":[{"id":"1-1","children":[{"id":"1-1-1"}]}]},{"id":"2","children":[{"id":"2-1"}]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) {console.log("expected:\n" + JSON.stringify(expected, null, 2));console.log("actual:\n" + JSON.stringify(actual, null, 2))}
else console.log(true);
}
{
let actual = buildTree([{"id":"1","children":[]},{"id":"1-1","children":[]},{"id":"1-1-1"},{"id":"2","children":[]}])
let expected = [{"id":"1","children":[{"id":"1-1","children":[{"id":"1-1-1"}]}]},{"id":"2","children":[]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) {console.log("expected:\n" + JSON.stringify(expected, null, 2));console.log("actual:\n" + JSON.stringify(actual, null, 2))}
else console.log(true);
}
{
let actual = buildTree([{"id":"1","children":[]},{"id":"1-1","children":[]},{"id":"1-1-1"},{"id":"1-1-2"}])
let expected = [{"id":"1","children":[{"id":"1-1","children":[{"id":"1-1-1"},{"id":"1-1-2"}]}]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) {console.log("expected:\n" + JSON.stringify(expected, null, 2));console.log("actual:\n" + JSON.stringify(actual, null, 2))}
else console.log(true);
}
{
let actual = buildTree([{"id":"1","children":[]},{"id":"1-1","children":[]},{"id":"1-1-1"}])
let expected = [{"id":"1","children":[{"id":"1-1","children":[{"id":"1-1-1"}]}]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) {console.log("expected:\n" + JSON.stringify(expected, null, 2));console.log("actual:\n" + JSON.stringify(actual, null, 2))}
else console.log(true);
}
{
let actual = buildTree([{"id":"1","children":[]},{"id":"1-1"},{"id":"2","children":[]},{"id":"2-1"}])
let expected = [{"id":"1","children":[{"id":"1-1"}]},{"id":"2","children":[{"id":"2-1"}]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) {console.log("expected:\n" + JSON.stringify(expected, null, 2));console.log("actual:\n" + JSON.stringify(actual, null, 2))}
else console.log(true);
}
{
let actual = buildTree([{"id":"1","children":[]},{"id":"1-1"},{"id":"1-2"}])
let expected = [{"id":"1","children":[{"id":"1-1"},{"id":"1-2"}]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) console.log(JSON.stringify(actual, null, 2))
else console.log(true);
}
{
let actual = buildTree([{"id":"1","children":[]},{"id":"1-1"}])
let expected = [{"id":"1","children":[{"id":"1-1"}]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) console.log(JSON.stringify(actual, null, 2))
else console.log(true);
}
{
let actual = buildTree([{id: "1","children":[]}, {id: "2","children":[]}])
let expected = [{"id":"1","children":[]},{"id":"2","children":[]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) console.log(JSON.stringify(actual, null, 2))
else console.log(true);
}
{
let actual = buildTree([{id: "1", "children": []}])
let expected = [{"id":"1","children":[]}];
let b = JSON.stringify(actual) === JSON.stringify(expected);
if (!b) console.log(JSON.stringify(actual, null, 2))
else console.log(true);
}

Try it online!

How can I map this array to a tree of nested object?

1 Answers1