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?

• The DIMM Reaper: I found plenty of questions asking how to create a tree from an array, but none converting back in the other direction, so I've posted the solution I came up with.

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

• The DIMM Reaper: Wow, I can't believe how little code that was, and it works perfectly. ES6 is great! Oh, and the level indicator wasn't necessary, I just added it to my implementation for illustration purposes.
• slowkot: Yeah, es6 and next are inspiring! Glad to read this! In addition, so far the first solution will be valid es5 if we replace lambdas with anonymous functions.

Answer 2

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 3

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!

• plalx: You should call your function flattenChildrenOf or something similar since it's disregarding the root at all times. Nothing says the root couldn't be an important node.
• Philip Stanislaus: Keep in mind that the above answer is recursive, and hence could be improved. Since I could not find a npm module which implements a O(n) solution, I created the following one (unit tested, 100% code coverage, only 0.5 kb in size and includes typings. Maybe it helps someone: npmjs.com/package/performant-array-to-tree

Answer 4

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 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:

enter image description here

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))
 }, [])
}

• Scott Sauyet: Welcome to StackOverflow! While this code may answer the question, providing additional context regarding how and/or why it solves the problem would improve the answer's long-term value. Note that flatMap can simplify this further, replacing the need for the reduce(push, concat) dance. I added an answer that does this.
• Community: Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.

Answer 9

Since this was recently revived, here is a solution using object-scan. Using a well documented and flexible library should make it easier to adjust the functionality if needed

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

<script type="module">
import objectScan from 'https://cdn.jsdelivr.net/npm/[email protected]/lib/index.min.js';
const obj = { 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: [] }] }] };
const r = objectScan(['**{children[*]}'], {
 rtn: 'value',
 afterFn: ({ result }) => result.map(({ children, ...rest }) => rest)
})(obj);
console.log(r);
/* => [
 { id: 4, title: 'company', parent: 2 },
 { id: 3, title: 'team', parent: 2 },
 { id: 2, title: 'about', parent: null },
 { id: 1, title: 'home', parent: null }
] */
</script>

Disclaimer: I'm the author of object-scan

Disclaimer: I'm the author of object-scan