How can I build a tree from a normalized tree list

Question

I have a normalized tree list:

const normalizedTree = {
  0: {
    id: 0,
    title: '(Root)',
    childIds: [1, 43, 47],
  },
  1: {
    id: 1,
    title: 'Earth',
    childIds: [2, 10, 19, 27, 35],
  },
  2: {
    id: 2,
    title: 'Africa',
    childIds: [3, 4, 5, 6, 7, 8, 9],
  },
  3: {
    id: 3,
    title: 'Botswana',
    childIds: [],
  },
  4: {
    id: 4,
    title: 'Egypt',
    childIds: [],
  },
  5: {
    id: 5,
    title: 'Kenya',
    childIds: [],
  },
  6: {
    id: 6,
    title: 'Madagascar',
    childIds: [],
  },
  7: {
    id: 7,
    title: 'Morocco',
    childIds: [],
  },
  8: {
    id: 8,
    title: 'Nigeria',
    childIds: [],
  },
  9: {
    id: 9,
    title: 'South Africa',
    childIds: [],
  },
  10: {
    id: 10,
    title: 'Americas',
    childIds: [11, 12, 13, 14, 15, 16, 17, 18],
  },
  11: {
    id: 11,
    title: 'Argentina',
    childIds: [],
  },
  12: {
    id: 12,
    title: 'Brazil',
    childIds: [],
  },
  13: {
    id: 13,
    title: 'Barbados',
    childIds: [],
  },
  14: {
    id: 14,
    title: 'Canada',
    childIds: [],
  },
  15: {
    id: 15,
    title: 'Jamaica',
    childIds: [],
  },
  16: {
    id: 16,
    title: 'Mexico',
    childIds: [],
  },
  17: {
    id: 17,
    title: 'Trinidad and Tobago',
    childIds: [],
  },
  18: {
    id: 18,
    title: 'Venezuela',
    childIds: [],
  },
  19: {
    id: 19,
    title: 'Asia',
    childIds: [20, 21, 22, 23, 24, 25, 26],
  },
  20: {
    id: 20,
    title: 'China',
    childIds: [],
  },
  21: {
    id: 21,
    title: 'Hong Kong',
    childIds: [],
  },
  22: {
    id: 22,
    title: 'India',
    childIds: [],
  },
  23: {
    id: 23,
    title: 'Singapore',
    childIds: [],
  },
  24: {
    id: 24,
    title: 'South Korea',
    childIds: [],
  },
  25: {
    id: 25,
    title: 'Thailand',
    childIds: [],
  },
  26: {
    id: 26,
    title: 'Vietnam',
    childIds: [],
  },
  27: {
    id: 27,
    title: 'Europe',
    childIds: [28, 29, 30, 31, 32, 33, 34],
  },
  28: {
    id: 28,
    title: 'Croatia',
    childIds: [],
  },
  29: {
    id: 29,
    title: 'France',
    childIds: [],
  },
  30: {
    id: 30,
    title: 'Germany',
    childIds: [],
  },
  31: {
    id: 31,
    title: 'Italy',
    childIds: [],
  },
  32: {
    id: 32,
    title: 'Portugal',
    childIds: [],
  },
  33: {
    id: 33,
    title: 'Spain',
    childIds: [],
  },
  34: {
    id: 34,
    title: 'Turkey',
    childIds: [],
  },
  35: {
    id: 35,
    title: 'Oceania',
    childIds: [36, 37, 38, 39, 40, 41, 42],
  },
  36: {
    id: 36,
    title: 'Australia',
    childIds: [],
  },
  37: {
    id: 37,
    title: 'Bora Bora (French Polynesia)',
    childIds: [],
  },
  38: {
    id: 38,
    title: 'Easter Island (Chile)',
    childIds: [],
  },
  39: {
    id: 39,
    title: 'Fiji',
    childIds: [],
  },
  40: {
    id: 40,
    title: 'Hawaii (the USA)',
    childIds: [],
  },
  41: {
    id: 41,
    title: 'New Zealand',
    childIds: [],
  },
  42: {
    id: 42,
    title: 'Vanuatu',
    childIds: [],
  },
  43: {
    id: 43,
    title: 'Moon',
    childIds: [44, 45, 46],
  },
  44: {
    id: 44,
    title: 'Rheita',
    childIds: [],
  },
  45: {
    id: 45,
    title: 'Piccolomini',
    childIds: [],
  },
  46: {
    id: 46,
    title: 'Tycho',
    childIds: [],
  },
  47: {
    id: 47,
    title: 'Mars',
    childIds: [48, 49],
  },
  48: {
    id: 48,
    title: 'Corn Town',
    childIds: [],
  },
  49: {
    id: 49,
    title: 'Green Hill',
    childIds: [],
  },
}

And I am trying to build out a tree from it as in:

const tree = {
  id: 0,
  title: '(Root)',
  childPlaces: [
    {
      id: 1,
      title: 'Earth',
      childPlaces: [
        {
          id: 2,
          title: 'Africa',
          childPlaces: [
            {
              id: 3,
              title: 'Botswana',
              childPlaces: [],
            },
            {
              id: 4,
              title: 'Egypt',
              childPlaces: [],
            },
            {
              id: 5,
              title: 'Kenya',
              childPlaces: [],
            },
            {
              id: 6,
              title: 'Madagascar',
              childPlaces: [],
            },
            {
              id: 7,
              title: 'Morocco',
              childPlaces: [],
            },
            {
              id: 8,
              title: 'Nigeria',
              childPlaces: [],
            },
            {
              id: 9,
              title: 'South Africa',
              childPlaces: [],
            },
          ],
        },
        {
          id: 10,
          title: 'Americas',
          childPlaces: [
            {
              id: 11,
              title: 'Argentina',
              childPlaces: [],
            },
            {
              id: 12,
              title: 'Brazil',
              childPlaces: [],
            },
            {
              id: 13,
              title: 'Barbados',
              childPlaces: [],
            },
            {
              id: 14,
              title: 'Canada',
              childPlaces: [],
            },
            {
              id: 15,
              title: 'Jamaica',
              childPlaces: [],
            },
            {
              id: 16,
              title: 'Mexico',
              childPlaces: [],
            },
            {
              id: 17,
              title: 'Trinidad and Tobago',
              childPlaces: [],
            },
            {
              id: 18,
              title: 'Venezuela',
              childPlaces: [],
            },
          ],
        },
        {
          id: 19,
          title: 'Asia',
          childPlaces: [
            {
              id: 20,
              title: 'China',
              childPlaces: [],
            },
            {
              id: 21,
              title: 'Hong Kong',
              childPlaces: [],
            },
            {
              id: 22,
              title: 'India',
              childPlaces: [],
            },
            {
              id: 23,
              title: 'Singapore',
              childPlaces: [],
            },
            {
              id: 24,
              title: 'South Korea',
              childPlaces: [],
            },
            {
              id: 25,
              title: 'Thailand',
              childPlaces: [],
            },
            {
              id: 26,
              title: 'Vietnam',
              childPlaces: [],
            },
          ],
        },
        {
          id: 27,
          title: 'Europe',
          childPlaces: [
            {
              id: 28,
              title: 'Croatia',
              childPlaces: [],
            },
            {
              id: 29,
              title: 'France',
              childPlaces: [],
            },
            {
              id: 30,
              title: 'Germany',
              childPlaces: [],
            },
            {
              id: 31,
              title: 'Italy',
              childPlaces: [],
            },
            {
              id: 32,
              title: 'Portugal',
              childPlaces: [],
            },
            {
              id: 33,
              title: 'Spain',
              childPlaces: [],
            },
            {
              id: 34,
              title: 'Turkey',
              childPlaces: [],
            },
          ],
        },
        {
          id: 35,
          title: 'Oceania',
          childPlaces: [
            {
              id: 36,
              title: 'Australia',
              childPlaces: [],
            },
            {
              id: 37,
              title: 'Bora Bora (French Polynesia)',
              childPlaces: [],
            },
            {
              id: 38,
              title: 'Easter Island (Chile)',
              childPlaces: [],
            },
            {
              id: 39,
              title: 'Fiji',
              childPlaces: [],
            },
            {
              id: 40,
              title: 'Hawaii (the USA)',
              childPlaces: [],
            },
            {
              id: 41,
              title: 'New Zealand',
              childPlaces: [],
            },
            {
              id: 42,
              title: 'Vanuatu',
              childPlaces: [],
            },
          ],
        },
      ],
    },
    {
      id: 43,
      title: 'Moon',
      childPlaces: [
        {
          id: 44,
          title: 'Rheita',
          childPlaces: [],
        },
        {
          id: 45,
          title: 'Piccolomini',
          childPlaces: [],
        },
        {
          id: 46,
          title: 'Tycho',
          childPlaces: [],
        },
      ],
    },
    {
      id: 47,
      title: 'Mars',
      childPlaces: [
        {
          id: 48,
          title: 'Corn Town',
          childPlaces: [],
        },
        {
          id: 49,
          title: 'Green Hill',
          childPlaces: [],
        },
      ],
    },
  ],
}

Here is my attempt:

function buildTree(normalizedTree) {
  const root = {
    id: 0,
    title: '(Root)',
    childPlaces: [],
  }

  let parent = root

  for (const node of Object.values(normalizedTree)) {
    const newNode = {
      id: node.id,
      title: node.title,
      childPlaces: [],
    }

    if (normalizedTree[parent.id].childIds.includes(node.id)) {
      parent.childPlaces.push(newNode)
    }
  }

  return root
}

The current solution only outputs the first level of the tree:

{
  id: 0,
  title: '(Root)',
  childPlaces: [
    { id: 1, title: 'Earth', childPlaces: [] },
    { id: 43, title: 'Moon', childPlaces: [] },
    { id: 47, title: 'Mars', childPlaces: [] }
  ]
}

I realized I needed to advance the parent pointer somewhere in my algorithms but I couldn't figure out how.

Answer 1

You need a recursive method - start at the root ID and work through its childIds and so on, that way each time you're iterating over an ID you'll have a reference to the parent object and can put it in the right childPlaces array. With your current approach, unless you've created some of the nested structure already and can identify the parent from an ID, you can't really do much with a created node.

const normalizedTree={0:{id:0,title:"(Root)",childIds:[1,43,47]},1:{id:1,title:"Earth",childIds:[2,10,19,27,35]},2:{id:2,title:"Africa",childIds:[3,4,5,6,7,8,9]},3:{id:3,title:"Botswana",childIds:[]},4:{id:4,title:"Egypt",childIds:[]},5:{id:5,title:"Kenya",childIds:[]},6:{id:6,title:"Madagascar",childIds:[]},7:{id:7,title:"Morocco",childIds:[]},8:{id:8,title:"Nigeria",childIds:[]},9:{id:9,title:"South Africa",childIds:[]},10:{id:10,title:"Americas",childIds:[11,12,13,14,15,16,17,18]},11:{id:11,title:"Argentina",childIds:[]},12:{id:12,title:"Brazil",childIds:[]},13:{id:13,title:"Barbados",childIds:[]},14:{id:14,title:"Canada",childIds:[]},15:{id:15,title:"Jamaica",childIds:[]},16:{id:16,title:"Mexico",childIds:[]},17:{id:17,title:"Trinidad and Tobago",childIds:[]},18:{id:18,title:"Venezuela",childIds:[]},19:{id:19,title:"Asia",childIds:[20,21,22,23,24,25,26]},20:{id:20,title:"China",childIds:[]},21:{id:21,title:"Hong Kong",childIds:[]},22:{id:22,title:"India",childIds:[]},23:{id:23,title:"Singapore",childIds:[]},24:{id:24,title:"South Korea",childIds:[]},25:{id:25,title:"Thailand",childIds:[]},26:{id:26,title:"Vietnam",childIds:[]},27:{id:27,title:"Europe",childIds:[28,29,30,31,32,33,34]},28:{id:28,title:"Croatia",childIds:[]},29:{id:29,title:"France",childIds:[]},30:{id:30,title:"Germany",childIds:[]},31:{id:31,title:"Italy",childIds:[]},32:{id:32,title:"Portugal",childIds:[]},33:{id:33,title:"Spain",childIds:[]},34:{id:34,title:"Turkey",childIds:[]},35:{id:35,title:"Oceania",childIds:[36,37,38,39,40,41,42]},36:{id:36,title:"Australia",childIds:[]},37:{id:37,title:"Bora Bora (French Polynesia)",childIds:[]},38:{id:38,title:"Easter Island (Chile)",childIds:[]},39:{id:39,title:"Fiji",childIds:[]},40:{id:40,title:"Hawaii (the USA)",childIds:[]},41:{id:41,title:"New Zealand",childIds:[]},42:{id:42,title:"Vanuatu",childIds:[]},43:{id:43,title:"Moon",childIds:[44,45,46]},44:{id:44,title:"Rheita",childIds:[]},45:{id:45,title:"Piccolomini",childIds:[]},46:{id:46,title:"Tycho",childIds:[]},47:{id:47,title:"Mars",childIds:[48,49]},48:{id:48,title:"Corn Town",childIds:[]},49:{id:49,title:"Green Hill",childIds:[]}};

const buildTree = (id) => {
  const { title, childIds } = normalizedTree[id];
  return { id, title, childPlaces: childIds.map(buildTree) };
};
const tree = buildTree(0); // root ID
console.log(tree);

Doing it without recursion would be uglier. I suppose you could map the normalizedTree to another one, where each object has a childPlaces array instead of childIds, then iterate over the original tree and push each child ID to the new tree's array, then finally take the root object to get the structure you want.

const normalizedTree={0:{id:0,title:"(Root)",childIds:[1,43,47]},1:{id:1,title:"Earth",childIds:[2,10,19,27,35]},2:{id:2,title:"Africa",childIds:[3,4,5,6,7,8,9]},3:{id:3,title:"Botswana",childIds:[]},4:{id:4,title:"Egypt",childIds:[]},5:{id:5,title:"Kenya",childIds:[]},6:{id:6,title:"Madagascar",childIds:[]},7:{id:7,title:"Morocco",childIds:[]},8:{id:8,title:"Nigeria",childIds:[]},9:{id:9,title:"South Africa",childIds:[]},10:{id:10,title:"Americas",childIds:[11,12,13,14,15,16,17,18]},11:{id:11,title:"Argentina",childIds:[]},12:{id:12,title:"Brazil",childIds:[]},13:{id:13,title:"Barbados",childIds:[]},14:{id:14,title:"Canada",childIds:[]},15:{id:15,title:"Jamaica",childIds:[]},16:{id:16,title:"Mexico",childIds:[]},17:{id:17,title:"Trinidad and Tobago",childIds:[]},18:{id:18,title:"Venezuela",childIds:[]},19:{id:19,title:"Asia",childIds:[20,21,22,23,24,25,26]},20:{id:20,title:"China",childIds:[]},21:{id:21,title:"Hong Kong",childIds:[]},22:{id:22,title:"India",childIds:[]},23:{id:23,title:"Singapore",childIds:[]},24:{id:24,title:"South Korea",childIds:[]},25:{id:25,title:"Thailand",childIds:[]},26:{id:26,title:"Vietnam",childIds:[]},27:{id:27,title:"Europe",childIds:[28,29,30,31,32,33,34]},28:{id:28,title:"Croatia",childIds:[]},29:{id:29,title:"France",childIds:[]},30:{id:30,title:"Germany",childIds:[]},31:{id:31,title:"Italy",childIds:[]},32:{id:32,title:"Portugal",childIds:[]},33:{id:33,title:"Spain",childIds:[]},34:{id:34,title:"Turkey",childIds:[]},35:{id:35,title:"Oceania",childIds:[36,37,38,39,40,41,42]},36:{id:36,title:"Australia",childIds:[]},37:{id:37,title:"Bora Bora (French Polynesia)",childIds:[]},38:{id:38,title:"Easter Island (Chile)",childIds:[]},39:{id:39,title:"Fiji",childIds:[]},40:{id:40,title:"Hawaii (the USA)",childIds:[]},41:{id:41,title:"New Zealand",childIds:[]},42:{id:42,title:"Vanuatu",childIds:[]},43:{id:43,title:"Moon",childIds:[44,45,46]},44:{id:44,title:"Rheita",childIds:[]},45:{id:45,title:"Piccolomini",childIds:[]},46:{id:46,title:"Tycho",childIds:[]},47:{id:47,title:"Mars",childIds:[48,49]},48:{id:48,title:"Corn Town",childIds:[]},49:{id:49,title:"Green Hill",childIds:[]}};

const buildNormalizedTreeWithChildPlaces = () => {
  const newTree = {};
  for (const node of Object.values(normalizedTree)) {
    const newNode = {
      id: node.id,
      title: node.title,
      childPlaces: [],
    };
    newTree[node.id] = newNode;
  }
  for (const [id, node] of Object.entries(normalizedTree)) {
    for (const childId of node.childIds) {
      newTree[id].childPlaces.push(newTree[childId]);
    }
  }
  return newTree;
};
const tree = buildNormalizedTreeWithChildPlaces();
console.log(tree[0]); // root ID

Answer 2

You have this:

parent.childPlaces.push(newNode)

but it seems parent is always root.

Another approach is delaying the childPlaces data:

function buildTree(normalized)
{
  const nodesArray = Object.values(normalizedTree);
  const idNodeMap = {};
  const children = new Set();
  // generate tree nodes without their children (delay the children)
  nodesArray.forEach(node => {
    idNodeMap[node.id] = {
        id: node.id,
        title: node.title,
        childPlaces: []
    };
  });
  // add the children (delayed)
  nodesArray.forEach(node => {
    node.childIds.forEach(id => {
        const child = idNodeMap[id];
        children.add(child);
        idNodeMap[node.id]
            .childPlaces
            .push(child);
    });
  });
  // find the root
  return Object.values(idNodeMap).find(node => !children.has(node));
}

A simpler approach is saving the nodes in a map and take advantage of the references. It instantiates empty objects for the children, if they're not found in that map.

function buildTree(normalized)
{
  const idNodesMap = {};
  const children = new Set();
  Object.values(normalizedTree)
    .forEach(node => {
      const obj = idNodesMap[node.id] ?? {};
      obj.id = node.id;
      obj.title = node.title;
      obj.childPlaces = node.childIds.map(childId => {
        const child = idNodesMap[childId] ?? {};
            idNodesMap[childId] = child;
            children.add(child);
            return child;
        });
        idNodesMap[node.id] = obj;
    });
    return Object.values(idNodesMap).find(node => !children.has(node));;
}

Here's a shorter solution, using recursion (it assumes the root ID is 0):

function buildTree(normalized, id=0)
{
  const node = normalized[id];
  return {
    id: node.id,
    title: node.title,
    childPlaces: node.childIds.map(id => buildTree(normalized, id)),
  };
}

Answer 3

The following allow you to create the tree with 1 iteration.

const normalizedTree={0:{id:0,title:"(Root)",childIds:[1,43,47]},1:{id:1,title:"Earth",childIds:[2,10,19,27,35]},2:{id:2,title:"Africa",childIds:[3,4,5,6,7,8,9]},3:{id:3,title:"Botswana",childIds:[]},4:{id:4,title:"Egypt",childIds:[]},5:{id:5,title:"Kenya",childIds:[]},6:{id:6,title:"Madagascar",childIds:[]},7:{id:7,title:"Morocco",childIds:[]},8:{id:8,title:"Nigeria",childIds:[]},9:{id:9,title:"South Africa",childIds:[]},10:{id:10,title:"Americas",childIds:[11,12,13,14,15,16,17,18]},11:{id:11,title:"Argentina",childIds:[]},12:{id:12,title:"Brazil",childIds:[]},13:{id:13,title:"Barbados",childIds:[]},14:{id:14,title:"Canada",childIds:[]},15:{id:15,title:"Jamaica",childIds:[]},16:{id:16,title:"Mexico",childIds:[]},17:{id:17,title:"Trinidad and Tobago",childIds:[]},18:{id:18,title:"Venezuela",childIds:[]},19:{id:19,title:"Asia",childIds:[20,21,22,23,24,25,26]},20:{id:20,title:"China",childIds:[]},21:{id:21,title:"Hong Kong",childIds:[]},22:{id:22,title:"India",childIds:[]},23:{id:23,title:"Singapore",childIds:[]},24:{id:24,title:"South Korea",childIds:[]},25:{id:25,title:"Thailand",childIds:[]},26:{id:26,title:"Vietnam",childIds:[]},27:{id:27,title:"Europe",childIds:[28,29,30,31,32,33,34]},28:{id:28,title:"Croatia",childIds:[]},29:{id:29,title:"France",childIds:[]},30:{id:30,title:"Germany",childIds:[]},31:{id:31,title:"Italy",childIds:[]},32:{id:32,title:"Portugal",childIds:[]},33:{id:33,title:"Spain",childIds:[]},34:{id:34,title:"Turkey",childIds:[]},35:{id:35,title:"Oceania",childIds:[36,37,38,39,40,41,42]},36:{id:36,title:"Australia",childIds:[]},37:{id:37,title:"Bora Bora (French Polynesia)",childIds:[]},38:{id:38,title:"Easter Island (Chile)",childIds:[]},39:{id:39,title:"Fiji",childIds:[]},40:{id:40,title:"Hawaii (the USA)",childIds:[]},41:{id:41,title:"New Zealand",childIds:[]},42:{id:42,title:"Vanuatu",childIds:[]},43:{id:43,title:"Moon",childIds:[44,45,46]},44:{id:44,title:"Rheita",childIds:[]},45:{id:45,title:"Piccolomini",childIds:[]},46:{id:46,title:"Tycho",childIds:[]},47:{id:47,title:"Mars",childIds:[48,49]},48:{id:48,title:"Corn Town",childIds:[]},49:{id:49,title:"Green Hill",childIds:[]}};

function buildTree(normalizedTree, rootId) {
  const nodes = Object.values(normalizedTree);
  const nodeMap = new Map(nodes.map(node => [node.id, { ...node }]));
  
  for(let node of nodes) {
      const n = nodeMap.get(node.id); if (n == null) continue;
      n.childPlaces = n.childIds.map(childId => nodeMap.get(childId));
      delete n.childIds;
  }
  return nodeMap.get(rootId);
}
console.log(buildTree(normalizedTree, 0));