Creating a tree from a flat list using lodash

Question

I am trying to create a category tree using the array of json objects below. I want to set a category as a child of another category if its parent equals the id of the other, and I want the posts also to be a children of that category instead of having a separate field for posts, I'll add a flag field that if it is a category or not isParent.

It looks like its working alright, but as you may see, if a category has both category and post as child, it'll only show the categories. Another problem with that is if the post has a null value on its array, it will still push them as children.

What are the mistakes in my code, or is there a simpler or better solution to this?

var tree = unflatten(getData());
var pre = document.createElement('pre');
console.log(tree);
pre.innerText = JSON.stringify(tree, null, 4);

document.body.appendChild(pre);

function unflatten(array, parent, tree) {
  tree = typeof tree !== 'undefined' ? tree : [];
  parent = typeof parent !== 'undefined' ? parent : {
    id: 0
  };
  _.map(array, function(arr) {
    _.set(arr, 'isParent', true);
  });
  var children = _.filter(array, function(child) {
    return child.parent == parent.id;
  });

  if (!_.isEmpty(children)) {
    if (parent.id == 0) {
      tree = children;
    } else {
      parent['children'] = children;
    }
    _.each(children, function(child) {
      var posts = _.map(child.posts, function(post) {
        return _.set(post, 'isParent', false);
      });
      child['children'] = posts;
      delete child.posts;
      unflatten(array, child);
    });
  }

  return tree;

}

function getData() {
  return [{
    "id": "c1",
    "parent": "",
    "name": "foo",
    "posts": [{
      "id": "p1"
    }]
  }, {
    "id": "c2",
    "parent": "1",
    "name": "bar",
    "posts": [{
      "id": "p2"
    }]
  }, {
    "id": "c3",
    "parent": "",
    "name": "bazz",
    "posts": [
      null
    ]
  }, {
    "id": "c4",
    "parent": "3",
    "name": "sna",
    "posts": [{
      "id": "p3"
    }]
  }, {
    "id": "c5",
    "parent": "3",
    "name": "ney",
    "posts": [{
      "id": "p4"
    }]
  }, {
    "id": "c6",
    "parent": "5",
    "name": "tol",
    "posts": [{
      "id": "p5"
    }, {
      "id": "p6"
    }]
  }, {
    "id": "c7",
    "parent": "5",
    "name": "zap",
    "posts": [{
      "id": "p7"
    }, {
      "id": "p8"
    }, {
      "id": "p9"
    }]
  }, {
    "id": "c8",
    "parent": "",
    "name": "quz",
    "posts": [
      null
    ]
  }, {
    "id": "c9",
    "parent": "8",
    "name": "meh",
    "posts": [{
      "id": "p10"
    }, {
      "id": "p11"
    }]
  }, {
    "id": "c10",
    "parent": "8",
    "name": "ror",
    "posts": [{
      "id": "p12"
    }, {
      "id": "p13"
    }]
  }, {
    "id": "c11",
    "parent": "",
    "name": "gig",
    "posts": [{
      "id": "p14"
    }]
  }, {
    "id": "c12",
    "name": "xylo",
    "parent": "",
    "posts": [{
      "id": "p15"
    }]
  }, {
    "id": "c13",
    "parent": "",
    "name": "grr",
    "posts": [{
      "id": "p16"
    }, {
      "id": "p17"
    }, {
      "id": "p14"
    }, {
      "id": "p18"
    }, {
      "id": "p19"
    }, {
      "id": "p20"
    }]
  }]
}

<script src="//cdn.jsdelivr.net/lodash/3.10.1/lodash.min.js"></script>

Expected Output

So the expected output will be more like:

[
   {
       id: 'c1',
       isParent: true,
       children: [
          {
             id: 'c2',
             isParent: true,
             children: []
          },
          {
             id: 'p1'
             isParent: false
          }
       ]
   }
]

And so on..

Beneficial

Answer 1

Your code is very imperative. Try focusing on the "big picture" of data flow instead of writing code by trial-and-error. It's harder, but you get better results (and, in fact, usually it's faster) :)

My idea is to first group the categories by their parents. This is the first line of my solution and it actually becomes much easier after that.

_.groupBy and _.keyBy help a lot here:

function makeCatTree(data) {
    var groupedByParents = _.groupBy(data, 'parent');
    var catsById = _.keyBy(data, 'id');
    _.each(_.omit(groupedByParents, ''), function(children, parentId) {
        catsById['c' + parentId].children = children; 
    });
    _.each(catsById, function(cat) {
        // isParent will be true when there are subcategories (this is not really a good name, btw.)
        cat.isParent = !_.isEmpty(cat.children); 
        // _.compact below is just for removing null posts
        cat.children = _.compact(_.union(cat.children, cat.posts));
        // optionally, you can also delete cat.posts here.
    });
    return groupedByParents[''];
}

I recommend trying each part in the developer console, then it becomes easy to understand.

Lawrencelawrencium

In lodash 4 .indexBy got renamed to .keyBy – Addams

Sorry, I've a doubt in _.omit(groupedByParents, ''). Isn't the same to use just groupedByParents ? – Skep

It removes the group with nodes that have no parent. – Lawrencelawrencium

Answer 2

I have made a small fidde that I think that is what you want.

http://jsfiddle.net/tx3uwhke/

var tree = buildTree(getData());
var pre = document.getElementById('a');
var jsonString = JSON.stringify(tree, null, 4);
console.log(jsonString);
pre.innerHTML = jsonString;

document.body.appendChild(pre);

function buildTree(data, parent){
    var result = [];
    parent = typeof parent !== 'undefined' ? parent : {id:""};
    children = _.filter(data, function(value){
        return value.parent === parent.id;
    });
    if(!_.isEmpty(children)){
        _.each(children, function(child){
            if (child != null){
                result.push(child);
                if(!_.isEmpty(child.posts)){
                    var posts = _.filter(child.posts, function(post){
                        return post !== null && typeof post !== 'undefined';
                    });
                    if(!_.isEmpty(posts)){
                        _.forEach(posts, function(post){
                            post.isParent = false;
                        });
                    }
                    result = _.union(result, posts);
                    delete child.posts;
                }
                ownChildren = buildTree(data, child);
                if(!_.isEmpty(ownChildren)){
                    child.isParent = true;
                    child.children = ownChildren;
                }else{
                    child.isParent = false;
                }
            }
        });
    }
    return result;
}

EDIT: made a new fiddle to contain the isParent part you can find it here

Hammerlock

one last bit, where should I add the isParentFlag – Beneficial

If this reply solved your question, please mark ik as solved. – Hammerlock

yeah, you don't have to rush things, i'm still evaluating if there's a simpler way to do this, – Beneficial

Answer 3

While this problem looks simple, I can remember to have struggled achieving it in a simple way. I therefore created a generic util to do so

You only have to write maximum 3 custom callbacks methods.

Here is an example:

import { flattenTreeItemDeep, treeItemFromList } from './tree.util';
import { sortBy } from 'lodash';


    const listItems: Array<ListItem> = [
      // ordered list arrival
      { id: 1, isFolder: true, parent: null },
      { id: 2, isFolder: true, parent: 1 },
      { id: 3, isFolder: false, parent: 2 },
      // unordered arrival
      { id: 4, isFolder: false, parent: 5 },
      { id: 5, isFolder: true, parent: 1 },
      // empty main level folder
      { id: 6, isFolder: true, parent: null },
      // orphan main level file
      { id: 7, isFolder: false, parent: null },
    ];

    const trees = treeItemFromList(
      listItems,
      (listItem) => listItem.isFolder, // return true if the listItem contains items
      (parent, leafChildren) => parent.id === leafChildren.parent, // return true if the leaf children is contained in the parent
      (parent, folderChildren) => parent.id === folderChildren.parent // return true if the children is contained in the parent
    );

console.log(trees);
/*
[
  {
    children: [
      {
        children: [{ data: { id: 3, isFolder: false, parent: 2 }, isLeaf: true }],
        data: { id: 2, isFolder: true, parent: 1 },
        isLeaf: false,
      },
      {
        children: [{ data: { id: 4, isFolder: false, parent: 5 }, isLeaf: true }],
        data: { id: 5, isFolder: true, parent: 1 },
        isLeaf: false,
      },
    ],
    data: { id: 1, isFolder: true, parent: null },
    isLeaf: false,
  },
  { children: [], data: { id: 6, isFolder: true, parent: null }, isLeaf: false },
  {
    data: {
      id: 7,
      isFolder: false,
      parent: null,
    },
    isLeaf: true,
  },
]
*/

I did not check with your example as all cases are different, you however need to implement only 3 methods to let the algorithm build the tree for you:

1. If the item is a folder or a leaf (in your case just check if the children contain any non falsy item) i.e. listItem.posts.some((value)=>!!value)
2. if a parent contains the leaf child, (parent, child) => !!parent.posts.filter((val)=>!!val).find(({id})=>child.id === id)
3. if a parent contains the folder: optional if this is the same logic as for a leaf child.

Cabe

Answer 4

flaten data：

const data = [
  {
    id: '1',
    label: 'Node 1',
  },
  {
    id: '2',
    parentId: '1',
    label: 'Node 2',
  },
  {
    id: '3',
    parentId: '1',
    label: 'Node 3',
  },
  {
    id: '4',
    parentId: '2',
    label: 'Node 4',
  },
  {
    id: '5',
    parentId: '2',
    label: 'Node 5',
  },
  {
    id: '6',
    parentId: '4',
    label: 'Node 6',
  },
]

converFuntion：

const convertToTree = (data: any[], rootId: string = 'root') => {
  const mappedById = _.keyBy(data, 'id');
  const groupedByParentId = _.groupBy(data, (item) => {
    if (item.parentId) {
      return item.parentId;
    }
    return 'root';
  });
  const result = _.mapValues(groupedByParentId, (children, parentId) => {
    const parent = mappedById[parentId];
    if (parent) {
      parent.children = children;
    } else {
      return children;
    }
    return parent;
  });
  return result[rootId]
};

use demo 1：

convertToTree(data)

result：

[
    {
        "id": "1",
        "label": "Node 1",
        "children": [
            {
                "id": "2",
                "parentId": "1",
                "label": "Node 2",
                "children": [
                    {
                        "id": "4",
                        "parentId": "2",
                        "label": "Node 4",
                        "children": [
                            {
                                "id": "6",
                                "parentId": "4",
                                "label": "Node 6"
                            }
                        ]
                    },
                    {
                        "id": "5",
                        "parentId": "2",
                        "label": "Node 5"
                    }
                ]
            },
            {
                "id": "3",
                "parentId": "1",
                "label": "Node 3"
            }
        ]
    }
]

use demo 2：

convertToTree(data, '2')

result：

{
    "id": "2",
    "parentId": "1",
    "label": "Node 2",
    "children": [
        {
            "id": "4",
            "parentId": "2",
            "label": "Node 4",
            "children": [
                {
                    "id": "6",
                    "parentId": "4",
                    "label": "Node 6"
                }
            ]
        },
        {
            "id": "5",
            "parentId": "2",
            "label": "Node 5"
        }
    ]
}

Carbine