Construct flat array from tree of objects

Question

Suppose I have a tree of objects like the following, perhaps created using the excellent algorithm found here: https://stackoverflow.com/a/22367819/3123195

{
    "children": [{
        "id": 1,
        "title": "home",
        "parent": null,
        "children": []
    }, {
        "id": 2,
        "title": "about",
        "parent": null,
        "children": [{
            "id": 3,
            "title": "team",
            "parent": 2,
            "children": []
        }, {
            "id": 4,
            "title": "company",
            "parent": 2,
            "children": []
        }]
    }]
}

(Specifically in this example, the array returned by that function is nested as the children array property inside an otherwise empty object.)

How would I convert it back to a flat array?

Answer 1

Hope your are familiar with es6:

let flatten = (children, extractChildren) => Array.prototype.concat.apply(
  children, 
  children.map(x => flatten(extractChildren(x) || [], extractChildren))
);

let extractChildren = x => x.children;

let flat = flatten(extractChildren(treeStructure), extractChildren)
               .map(x => delete x.children && x);

UPD:

Sorry, haven't noticed that you need to set parent and level. Please find the new function below:

let flatten = (children, getChildren, level, parent) => Array.prototype.concat.apply(
  children.map(x => ({ ...x, level: level || 1, parent: parent || null })), 
  children.map(x => flatten(getChildren(x) || [], getChildren, (level || 1) + 1, x.id))
);

https://jsbin.com/socono/edit?js,console

Answer 2

This function will do the job, plus it adds a level indicator to each object. Immediate children of treeObj will be level 1, their children will be level 2, etc. The parent properties are updated as well.

function flatten(treeObj, idAttr, parentAttr, childrenAttr, levelAttr) {
    if (!idAttr) idAttr = 'id';
    if (!parentAttr) parentAttr = 'parent';
    if (!childrenAttr) childrenAttr = 'children';
    if (!levelAttr) levelAttr = 'level';

    function flattenChild(childObj, parentId, level) {
        var array = []; 

        var childCopy = angular.extend({}, childObj);
        childCopy[levelAttr] = level;
        childCopy[parentAttr] = parentId;
        delete childCopy[childrenAttr];
        array.push(childCopy);

        array = array.concat(processChildren(childObj, level));

        return array;
    };

    function processChildren(obj, level) {
        if (!level) level = 0;
        var array = [];

        obj[childrenAttr].forEach(function(childObj) {
            array = array.concat(flattenChild(childObj, obj[idAttr], level+1));
        });

        return array;
    };

    var result = processChildren(treeObj);
    return result;
};

This solution takes advantage of Angular's angular.extend() function to perform a copy of the child object. Wiring this up with any other library's equivalent method or a native function should be a trivial change.

The output given for the above example would be:

[{
    "id": 1,
    "title": "home",
    "parent": null,
    "level": 1
}, {
    "id": 2,
    "title": "about",
    "parent": null,
    "level": 1
}, {
    "id": 3,
    "title": "team",
    "parent": 2,
    "level": 2
}, {
    "id": 4,
    "title": "company",
    "parent": 2,
    "level": 2
}]

It is also worth noting that this function does not guarantee the array will be ordered by id; it will be based on the order in which the individual objects were encountered during the operation.

Fiddle!

Answer 3

Try following this only assumes each item is having children property

class TreeStructureHelper {
   public toArray(nodes: any[], arr: any[]) {
    if (!nodes) {
      return [];
    }
    if (!arr) {
      arr = [];
    }
    for (var i = 0; i < nodes.length; i++) {
      arr.push(nodes[i]);
      this.toArray(nodes[i].children, arr);
    }
  return arr;
 }
}

Usage

 let treeNode =
 {
   children: [{
    id: 1,
    title: "home",
    parent: null,
    children: []
   }, {
    id: 2,
    title: "about",
    parent: null,
    children: [{
        id: 3,
        title: "team",
        parent: 2,
        children: []
     }, {
        id: 4,
        title: "company",
        parent: 2,
        children: []
     }]
   }]
 };
 let flattenArray = _treeStructureHelper.toArray([treeNode], []);

Answer 4

Since this has been brought up again by a new answer, it's worth looking at a modern simple approach:

const flatten = ({children}) =>
  children .flatMap (({children = [], ...rest}) => [rest, ...flatten ({children})])

let tree = {children: [{id: 1, title: "home", parent: null, children: []}, {id: 2, title: "about", parent: null, children: [{id: 3, title: "team", parent: 2, children: []}, {id: 4, title: "company", parent: 2, children: []}]}]}

console .log (flatten (tree))

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

Using Array.prototype.flatMap, we map the items in a flat array, recurring on their children property.

Answer 5

Here it goes my contribution:

function flatNestedList(nestedList, childrenName, parentPropertyName, idName, newFlatList, parentId) {

        if (newFlatList.length === 0)
            newFlatList = [];

        $.each(nestedList, function (i, item) {
            item[parentPropertyName] = parentId;
            newFlatList.push(item);
            if (item[childrenName] && item[childrenName].length > 0) {
                //each level
                flatNestedList(item[childrenName], childrenName, parentPropertyName, idName, newFlatList, item[idName]);
            }
        });

        for (var i in newFlatList)
            delete (newFlatList[i][childrenName]);
    }

Answer 6

This is data:

 const data = {
      id: '1',
      children: [
        {
          id: '2',
          children: [
            {
              id: '4',
              children: [
                {
                  id: '5'
                },
                {
                  id: '6'
                }
              ]
            },
            {
              id: '7'
            }
          ]
        },
        {
          id: '3',
          children: [
            {
              id: '8'
            },
            {
              id: '9'
            }
          ]
        }
      ]
    }

In React.JS just declare an array field in state and push items to that array.

  const getAllItemsPerChildren = item => {
    array.push(item);
    if (item.children) {
      return item.children.map(i => getAllItemsPerChildren(i));
    }
  }

After function call your array in state will hold all items as below:

Answer 7

One more

function flatten(root, parent=null, depth=0, key='id', flat=[], pick=() => {}) {
    flat.push({
        parent,
        [key]: root[key],
        depth: depth++,
        ...pick(root, parent, depth, key, flat)
    });
    
    if(Array.isArray(root.children)) {
        root.children.forEach(child => flatten(child, root[key], depth, key, flat, pick));
    }
}

let sample = {
    "id": 0,
    "children": [{
        "id": 1,
        "title": "home",
        "parent": null,
        "children": []
    }, {
        "id": 2,
        "title": "about",
        "parent": null,
        "children": [{
            "id": 3,
            "title": "team",
            "parent": 2,
            "children": []
        }, {
            "id": 4,
            "title": "company",
            "parent": 2,
            "children": []
        }]
    }]
};

let flat = [];

flatten(sample, null, 0, 'id', flat, root => ({ title: root.title }));

let expected = [
    {
        "id": 0,
        "parent": null,
        "depth": 0
    },
    {
        "id": 1,
        "parent": 0,
        "depth": 1,
        "title": "home"
    },
    {
        "id": 2,
        "parent": 0,
        "depth": 1,
        "title": "about"
    },
    {
        "id": 3,
        "parent": 2,
        "depth": 2,
        "title": "team"
    },
    {
        "id": 4,
        "parent": 2,
        "depth": 2,
        "title": "company"
    }
];

Answer 8

you can use a recursive function like this:

toFlat(items) {
  if(!items || !items.length) {
     return []
  }
  return items.reduce((totalItems, item) => {
    totalItems.push(item)
    return totalItems.concat(toFlat(item.children))
  }, [])
}