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

Question

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);

};

You've written a thorough description of your task and expected output, but you'll find people much more willing to help if you show what you have tried and where you are stuck. Post your code even if it isn't working and when practical post a [minimal reproducible example](https://stackoverflow.com/help/minimal-reproducible-example). — pilchard, Nov 02 '21 at 00:50
The function never uses the `parent` parameter. What is it for? — Barmar, Nov 02 '21 at 00:58
If you don't name your question more specifically it may end up closed. If you need help naming it better, please ask. — Slbox, Nov 02 '21 at 01:01
Parent is meant to be used to establish the starting parent I believe. I think I should be using it recursively to tell the program who the parent should be of each of the nested I.D's. both examples start it at null so It hasn't come up. I am trying to figure out how to do the problem at all and then working towards my other goals like establishing a working parent. — Mikel Fisher, Nov 02 '21 at 01:02

pilchard · Answer 1 · 2021-11-02T11:15:31.853

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.

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; }

I really like the answer but my understanding of JS is so limited I genuinely do not understand exactly how you are doing what you are doing in the code above. This week they are teaching me recursion and I am on this problem trying to figure out how to do it at all. I can understand a little of what you did but is there any way you can dumb down the solution for me a little? I am more confused about the arguments you use in reduce and the ??= operators you use. — Mikel Fisher, Nov 02 '21 at 01:23
That's fair, it's a little bit of magic leveraging the fact that objects are passed by reference, a side effect of which is that if you change it's properties in one place, they change in the other places it's referenced. see: [Is JavaScript a pass-by-reference or pass-by-value language?](https://stackoverflow.com/questions/518000/is-javascript-a-pass-by-reference-or-pass-by-value-language) for some opinionated discussion. — pilchard, Nov 02 '21 at 01:31
I added a more explicit refactor of my original. Hopefully it more clearly shows how the objects stored in the 'map' interact. — pilchard, Nov 02 '21 at 01:36
I appreciate you trying to walk me through this, I am still trying to figure out the recursive way I could do this but I feel like what you gave me has helped me along. Thank you! — Mikel Fisher, Nov 02 '21 at 01:36
The problem with recursion in this case is that for any given step you don't necessarily have all the intermediate steps, so ordering of the array becomes important. — pilchard, Nov 02 '21 at 01:41

score 0 · Answer 2 · answered Nov 02 '21 at 16:41

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.

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

2 Answers2