CODEWITHSUNDEEP
javascriptalgorithmtree
Goodwin
Goodwin

Reputation: 183

Javascript Recursion Tree Building

I am having an issue building a tree from a flat array. I am building a category -> subcategory tree in which the parent has subcategories as an array.

Here is what the flat array would look like:

[
  {
    "id": 1
  },
  {
    "id": 5,
  },
  {
    "id": 2,
    "parent_id": 1
  },
  {
    "id": 3,
    "parent_id": 1
  },
  {
    "id": 42,
    "parent_id": 5
  },
  {
    "id": 67,
    "parent_id": 5
  }
]

And this is what I need the result to look:

[
  {
    "id":1,
    "subcategories":[
      {
        "id":2,
        "parent_id":1
      },
      {
        "id":3,
        "parent_id":1
      }
    ]
  },
  {
    "id":5,
    "subcategories":[
      {
        "id":42,
        "parent_id":5
      },
      {
        "id":67,
        "parent_id":5
      }
    ]
  }
]

I have tried to do this recursively by recursively searching for children and attaching it as an array and continuing to do so until I hit the bottom of the barrel but I am getting a cyclic structure. It appears that the parent_id in traverse is always the id of the parent... any ideas:

tree(passingInFlatObjectHere);

function topLevel (data) {
  let blob = [];
  data.forEach((each) => {
    if (!each.parent_id) {
      blob.push(each);
    }
  });
  return blob;
}

function tree (data) {
  let blob = topLevel(data).map(function (each) {
    each.subcategories = traverse(data, each.id);
    return each;
  });
  return blob;
}

function traverse (data, parent_id) {
  let blob = [];
  if (!parent_id) {
    return blob;
  }
  data.forEach((each) => {
    if (each.id === parent_id) {
      each.subcategories = traverse(data, each.id);
      blob.push(each);
    }
  });
  return blob;
}

Upvotes: 0

Views: 2383

Answers (2)

user18577865
user18577865

Reputation:

First, you need install lodash with below command with npm:

npm i lodash

Second, you must import _ from lodash

import _ from "lodash";

Finally, run this function:

export const recursive_lists = (data) => {
  const grouped = _.groupBy(data, (item) => item. parent_id);

  function childrenOf(parent_id) {
    return (grouped[parent_id] || []).map((item) => ({
      id: item.id,
      child: childrenOf(item.id),
    }));
  }

  return childrenOf(null);
};

or

First:

<script src="https://cdn.jsdelivr.net/npm/[email protected]/lodash.min.js"></script>

Second:

function recursive_lists(data) {
  const grouped = _.groupBy(data, (item) => item.parent_id);

  function childrenOf(parent_id) {
    return (grouped[parent_id] || []).map((item) => ({
      id: item.id,
      child: childrenOf(item.id),
    }));
  }

  return childrenOf(null);
};

Upvotes: 0

idmean
idmean

Reputation: 14915

I don’t just want to help you fix your problem but would also like to help you take full advantage of ES6

First of all your topLevel function can be rewritten to this:

function topLevel(data) {
  return data.filter(node => !node.parent_id);
}

Neat isn’t it? I also would recommend slightly changing tree for consistency but that’s of course just stylistic.

function tree(data) {
  return topLevel(data).map(each => {
    each.subcategories = traverse(data, each.id);
    return each;
  });
}

No logic issues so far. traverse, however, contains one, when you check each.id === parent_id. Like this, the functions searches for the node whose id is parent_id. Obviously a mistake. You wanted each.parent_id === parent_id.

Your issue is solved now. Stop reading if I bother you. But you could also take advantage of filter here and remove that slightly superfluous early exit and rewrite your function to: 

function traverse(data, parentId) {
  const children = data.filter(each => each.parent_id === parentId);
  children.forEach(child => {
    child.subcategories = traverse(data, child.id);
  });
  return children;
}

Upvotes: 1

Related Questions