Trouble with a recursive problem in JavaScript. Creating a tree of objects based off an array of obj-CodePudding

Write a recursive function makeTree(categories, parent) that takes an array of categories objects, each of which have an id property, and a parent property and returns a nested tree of those objects using the parent properties to construct the tree.

A parent value of null means you are at the bottom of the tree and the category has no parent, so the default value parent is be null if no parent is provided.

Example 1:

Given an array of objects with id properties to create our tree:

const categories1 = [
    { id: 'animals', 'parent': null },
    { id: 'mammals', 'parent': 'animals' }
];

const tree1 = makeTree(categories1, null);

We should return a tree like this:

{
  animals: {
    mammals: {}
  }
}

Example 2: Now imagine we have a database that returns a bunch of rows of data:

const categories2 = [
    { id: 'animals', 'parent': null },
    { id: 'mammals', 'parent': 'animals' },
    { id: 'cats', 'parent': 'mammals' },
    { id: 'dogs', 'parent': 'mammals' },
    { id: 'chihuahua', 'parent': 'dogs' },
    { id: 'labrador', 'parent': 'dogs' },
    { id: 'persian', 'parent': 'cats' },
    { id: 'siamese', 'parent': 'cats' }
];

Then we call the function with the categories: const tree2 = makeTree(categories2, null);

The call above should return the tree below:

{
    animals: {
        mammals: {
            dogs: {
                chihuahua: {},
                labrador: {}
            },
            cats: {
                persian: {},
                siamese: {}
            }
        }
    } }

I have written ten different things but this is an example of one of my current failures, This is a practice problem but I cannot figure it out at all. I am not sure how to check through the second example object and find the correct keys to put everything in its place. I have thought about iterating backwards to create the individual animals and then place them into the parent objects one by one, but I cannot think of a way to do so.

const makeTree = (categories, parent,obj={}) =>
{




  if (categories.length === 0) return obj;

  let nextObj = categories[0];

  if (nextObj['parent'] === null) obj[nextObj['id']] = {};
  else {

    var cKey = nextObj['id'];

    obj[nextObj['parent']] = Object.assign(cKey);
    



  }

  categories.shift();

  return makeTree(categories, parent, obj);

};

CodePudding user response：

You don't actually need recursion here, you can simply reduce() the array keeping track of each node in one object (or Map) the final tree will be the object held by the null property which will hold all the top level parents.

I've shuffled the source array because order of the array shouldn't matter.

I've also logged the entire 'result' object that was used in the reduce, which is a flat object allowing you access to each node without worrying about how deeply nested it is. This object requires that you retrieve/assign both parent and child nodes to it on each iteration.

Original

const categories2 = [
  { id: 'dogs', parent: 'mammals' },
  { id: 'siamese', parent: 'cats' },
  { id: 'labrador', parent: 'dogs' },
  { id: 'animals', parent: null },
  { id: 'cats', parent: 'mammals' },
  { id: 'mammals', parent: 'animals' },
  { id: 'chihuahua', parent: 'dogs' },
  { id: 'persian', parent: 'cats' },
];

const result = categories2.reduce((map, { id: child, parent }) => {
  const _parent = (map[parent] ??= {});
  const _child = (map[child] ??= {});

  _parent[child] = _child;

  return map;
}, {});

const tree = result[null];
console.log('final tree: ', JSON.stringify(tree, null, 2));

// Logging the entire 'result' object shows the flat object that allows you to access each node without worrying about how deeply nested it is.
console.log('complete result object: ', JSON.stringify(result, null, 2));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Note: if the use of logical nullish assignment (??=) gives you problems it can be replaced with an OR (||) short-circuit

// const _parent = (map[parent] ??= {});
// const _child = (map[child] ??= {});

const _parent = map[parent] || (map[parent] = {});
const _child = map[child] || (map[child] = {});

Edit: More explicit syntax

Here is a refactoring of the above, but using a for...of loop which is a little clearer to read without the added syntax of the reduce(). Otherwise the logic is unchanged except that it uses two objects instead of one – one to serve as the final tree to which we assign all properties with null parents and a second that serves as an index of all the nodes to assist in building the tree.

Show code snippet

const categories2 = [
  { id: 'dogs', parent: 'mammals' },
  { id: 'siamese', parent: 'cats' },
  { id: 'labrador', parent: 'dogs' },
  { id: 'animals', parent: null },
  { id: 'cats', parent: 'mammals' },
  { id: 'mammals', parent: 'animals' },
  { id: 'chihuahua', parent: 'dogs' },
  { id: 'persian', parent: 'cats' },
];

const result = {};
const map = {};

for (const { id: child, parent } of categories2) {
  if (map[parent] === undefined) {
    map[parent] = {};
  }
  if (map[child] === undefined) {
    map[child] = {};
  }

  map[parent][child] = map[child];

  if (parent === null) {
    result[child] = map[child];
  }
}

console.log('result object: ', JSON.stringify(result, null, 2));

// Logging the result.map shows the flat object that allows you to access each node without worrying about how deeply nested it is.

console.log('node map used in reduce: ', JSON.stringify(map, null, 2));

.as-console-wrapper { max-height: 100% !important; top: 0; }

CodePudding user response：

A complete recursive solution, with tests.

// tree.js
function rootId(nodes) {
  return nodes.find((e) => e.parent === null).id;
}

function childIds(categories, parentId) {
  return categories.filter((c) => c.parent === parentId).map((c) => c.id);
}

function makeTree(categories, currentId) {
  if (currentId === null) {
    let rid = rootId(categories);
    return { [rid]: makeTree(categories, rid) };
  } else {
    let tree = {};
    childIds(categories, currentId).forEach((childId) => {
      tree[childId] = makeTree(categories, childId);
    });
    return tree;
  }
}

module.exports = makeTree;

// tree.test.js
const makeTree = require("./tree");

test("example 1", () => {
  const categories = [
    { id: "animals", parent: null },
    { id: "mammals", parent: "animals" },
  ];
  expect(makeTree(categories, null)).toStrictEqual({
    animals: {
      mammals: {},
    },
  });
});

test("example 2", () => {
  const categories = [
    { id: "animals", parent: null },
    { id: "mammals", parent: "animals" },
    { id: "cats", parent: "mammals" },
    { id: "dogs", parent: "mammals" },
    { id: "chihuahua", parent: "dogs" },
    { id: "labrador", parent: "dogs" },
    { id: "persian", parent: "cats" },
    { id: "siamese", parent: "cats" },
  ];
  expect(makeTree(categories, null)).toStrictEqual({
    animals: {
      mammals: {
        dogs: {
          chihuahua: {},
          labrador: {},
        },
        cats: {
          persian: {},
          siamese: {},
        },
      },
    },
  });
});

// package.json
{
  "name": "tree_js",
  "version": "1.0.0",
  "main": "index.js",
  "license": "MIT",
  "devDependencies": {
    "jest": "^27.3.1",
    "prettier": "^2.4.1"
  },
  "scripts": {
    "test": "jest"
  }
}

Run the tests with yarn test.