How to flatten a object tree in JavaScript

Question

I need to recursively turn this object tree into a single array with the order being drilled down so [parent, child, child, grandchild, grandchild, child, grandchild] etc...

Tried a bunch of stuff but I'm kind of stuck on this one. Any help would be amazing. Thanks all :)

One thing I tried is: function flatten(inititalTree) { var flattenedTree = [];

var treeObjClone = JSON.parse(JSON.stringify(inititalTree));
var children = treeObjClone.children

if(Object.keys(children).length > 0) {
    for (var key in children) {
        if (children.hasOwnProperty(key)) {
            var child = JSON.parse(JSON.stringify(children[key]));
            flattenedTree.push(child);

            var grandchild = child.children;

            if(Object.keys(grandchild).length > 0) {
                for (var iKey in grandchild) {
                    if (grandchild.hasOwnProperty(iKey)) {
                        var grandchildChild = JSON.parse(JSON.stringify(grandchild[iKey]));
                        [...flattenedTree, ...flatten(grandchildChild)];
                    }
                }
            }

        }
    }
}

return flattenedTree;

};

console.log(flatten(treeStructure))

var treeStructure = {
qty: 1,
itemId: "2158",
itemType: "Assembly",
serialNumberId: "2299",
replacedSerialNumber: null,
workOrderId: "23670",
hasSerial: true,
parentSerialNumberId: "",
assemblyBuildId: "",
children: {
    2161: {
        qty: 1,
        itemId: "2161",
        itemType: null,
        serialNumberId: "2293",
        replacedSerialNumber: null,
        hasSerial: true,
        workOrderId: null,
        parentSerialNumberId: "2299",
        assemblyBuildId: "23675",
        children: {
            2156: {
                qty: 1,
                itemId: "2156",
                itemType: null,
                serialNumberId: "2265",
                replacedSerialNumber: null,
                hasSerial: true,
                workOrderId: null,
                parentSerialNumberId: "2293",
                assemblyBuildId: "20259",
                children: {
                    2453: {
                        qty: 1,
                        itemId: "2453",
                        itemType: null,
                        serialNumberId: "2254",
                        replacedSerialNumber: null,
                        hasSerial: true,
                        workOrderId: null,
                        parentSerialNumberId: "2265",
                        assemblyBuildId: "18048",
                        "children": {}
                    },
                    2454: {
                        qty: 1,
                        itemId: "2454",
                        itemType: null,
                        serialNumberId: "2244",
                        replacedSerialNumber: null,
                        hasSerial: true,
                        workOrderId: null,
                        parentSerialNumberId: "2265",
                        assemblyBuildId: "18048",
                        "children": {}
                    }
                }
            },
            2157: {
                qty: 1,
                itemId: "2157",
                itemType: null,
                serialNumberId: "2292",
                replacedSerialNumber: null,
                hasSerial: true,
                workOrderId: null,
                parentSerialNumberId: "2293",
                assemblyBuildId: "20259",
                children: {
                    2832: {
                        qty: 1,
                        itemId: "2832",
                        itemType: null,
                        serialNumberId: "2227",
                        replacedSerialNumber: null,
                        hasSerial: true,
                        workOrderId: null,
                        parentSerialNumberId: "2292",
                        assemblyBuildId: "20256",
                        children: {
                            2827: {
                                qty: 19,
                                itemId: "2827",
                                itemType: null,
                                serialNumberId: "2200",
                                replacedSerialNumber: null,
                                hasSerial: true,
                                workOrderId: null,
                                parentSerialNumberId: "2227",
                                assemblyBuildId: "14176",
                                "children": {}
                            },
                            2832: {
                                qty: 0,
                                itemId: "2832",
                                itemType: null,
                                serialNumberId: null,
                                replacedSerialNumber: null,
                                hasSerial: false,
                                workOrderId: null,
                                parentSerialNumberId: "2227",
                                assemblyBuildId: "14176",
                                "children": {}
                            }
                        }
                    }
                }
            }
        }
    },
    2622: {
        qty: 1,
        itemId: "2622",
        itemType: null,
        serialNumberId: null,
        replacedSerialNumber: null,
        hasSerial: false,
        workOrderId: null,
        parentSerialNumberId: "2299",
        assemblyBuildId: "23675",
        "children": {}
    },
    2623: {
        qty: 3,
        itemId: "2623",
        itemType: null,
        serialNumberId: null,
        replacedSerialNumber: null,
        hasSerial: false,
        workOrderId: null,
        parentSerialNumberId: "2299",
        assemblyBuildId: "23675",
        "children": {}
    },
    2628: {
        qty: 1,
        itemId: "2628",
        itemType: null,
        serialNumberId: null,
        replacedSerialNumber: null,
        hasSerial: false,
        workOrderId: null,
        parentSerialNumberId: "2299",
        assemblyBuildId: "23675",
        "children": {}
    },
    2629: {
        qty: 1,
        itemId: "2629",
        itemType: null,
        serialNumberId: null,
        replacedSerialNumber: null,
        hasSerial: false,
        workOrderId: null,
        parentSerialNumberId: "2299",
        assemblyBuildId: "23675",
        "children": {}
    },
    2630: {
        qty: 1,
        itemId: "2630",
        itemType: null,
        serialNumberId: null,
        replacedSerialNumber: null,
        hasSerial: false,
        workOrderId: null,
        parentSerialNumberId: "2299",
        assemblyBuildId: "23675",
        "children": {}
    },
    2631: {
        qty: 1,
        itemId: "2631",
        itemType: null,
        serialNumberId: null,
        replacedSerialNumber: null,
        hasSerial: false,
        workOrderId: null,
        parentSerialNumberId: "2299",
        assemblyBuildId: "23675",
        "children": {}
    },
    2640: {
        qty: 1,
        itemId: "2640",
        itemType: null,
        serialNumberId: null,
        replacedSerialNumber: null,
        hasSerial: false,
        workOrderId: null,
        parentSerialNumberId: "2299",
        assemblyBuildId: "23675",
        "children": {}
    }
}

}

SimProch · Accepted Answer · 2022-05-11 07:37:50Z

2

So just to confirm, if I understand this correctly, you have a tree such as:

{
    "value": 1,
    "children": [
        {
            "value": 2,
            "children": [
                {
                    "value": 3,
                    "children": null
                },
                {
                    "value": 4,
                    "children": null
                }
            ]
        },
        {
            "value": 5,
            "children": [
                {
                    "value": 6,
                    "children": null
                },
                {
                    "value": 7,
                    "children": null
                }
            ]
        }
    ]
}

And you want the result to be (note that I only put values in there in order to simplify it, you can do it with the entire objects):

[1,2,5,3,4,6,7]

What you can do is use Breadth-first Search. The key to that is basically use a queue:

function BFS(rootNode) {
    const result = [];
    const queue = [];
    queue.push(rootNode);
    while (true) {
        let count = queue.length;
        if (count === 0) break;
        while (count > 0) {
            let node = queue.shift();
            result.push(node);
            node.children?.forEach(child => queue.push(child));
            count--
        }
    }
    return result;
}

Works for the input I sent above.

If you'd like the result to be [1,2,3,4,5,6,7] (so going one path down, then another, then another), you are looking for Depth-first search.

answered May 11, 2022 at 7:37

SimProch

1468 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Nadav Julius Over a year ago

The child key is itself a object of objects and not an array of objects

SimProch Over a year ago

@NadavJulius you can then just update the code to iterate over the keys: const children = Object.keys(node.children); children.forEach(i => doStuffHere())

Collectives™ on Stack Overflow

How to flatten a object tree in JavaScript

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related