Как сконвертировать плоский массив в дерево?

Question

[Mike]

Добрый вечер!

Друзья, помогите решить задачку, а то уже мозг плавится от перепробованных вариантов, но ни один не работает:
Есть плоский массив вида:

[
{id: 0, name: 'Main', path: '/', childs: [1,2]},
{id: 1, name: 'One', path: '/one', childs: [3]},
{id: 2, name: 'Two', path: '/two', childs: []},
{id: 3, name: 'Three', path: '/one/three', childs: []}
]

Его нужно преобразовать в дерево вида:

{
  name:  'Main',
  path: '/',
  children: [
    {
      name: 'One', 
      path: '/sub1',
      children': [
       {
          name: 'Three', 
          path: '/one/three',
          children: []
        }
      ]
    },
    {
      name: 'Two', 
      path: '/two',
      children: []
    }
  ]
}

Уровней вложенности может быть гораздо больше, но я сократил пример.

Comments

[Сергей Соколов]

у child'ов id всегда больше, чем у родителя?

[Mike]

Сергей Соколов, да

[Mike]

Сергей Соколов, JackShcherbakov написал совсем не то, что нужно...

[Сергей Соколов]

Mike, я вам предложил вариант с рекурсией

Answer 1

[Сергей Соколов]

1. Найти корневой элемент – в вашем случае это с наименьшим id
   
2. Далее рекурсивно вызывать функцию, которая получая на вход элемент дописывает ему детей по их id.
   

Чтобы быстрее по id находить весь элемент, данные в начале преобразовываются в «словарь» – объект, где свойства это id, а значения элементы.

var data = [
{id: 0, name: 'Main', path: '/', childs: [1,2]},
{id: 1, name: 'One', path: '/one', childs: [3]},
{id: 2, name: 'Two', path: '/two', childs: []},
{id: 3, name: 'Three', path: '/one/three', childs: []}
];

function makeTree(d) {
  var id, el, i, dict = {}, minId, r;
  
  function parseChildren(el) {
    var i, newEl;
    for( i = 0; i < el.childs.length; i++) {
      newEl = makeElement(dict[ el.childs[i] ]);
      parseChildren( newEl);
      el.children.push( newEl);
    }
    delete el.childs;
  }
  
  for( i = 0; i < d.length; i++) {
    el = d[i];
    id = el.id;
    if( typeof minId === 'undefined' || minId > id) minId = id;
    dict[id] = el;
  }

  r = makeElement( dict[minId] ); // root element
  parseChildren(r);
  return r;
}

function makeElement(arrElement) {
  return {
    name: arrElement.name,
    path: arrElement.path,
    childs: arrElement.childs,
    children: []
  };
}

var tree = makeTree(data);
/* {
	"name": "Main",
	"path": "/",
	"children": [{
		"name": "One",
		"path": "/one",
		"children": [{
			"name": "Three",
			"path": "/one/three",
			"children": []
		}]
	}, {
		"name": "Two",
		"path": "/two",
		"children": []
	}]
} */