Flatten an array with parent-child relationships so that all children are on the parent level

Question

Good morning, given the below data structure (in JSON for ease of reading)

[
{
    "parent": "root",
    "active": "1",
    "label": "Index",
    "route": "/",
    "children": [
        {
            "parent": "/",
            "active": "1",
            "label": "Products",
            "route": "/products",
            "children": [
                {
                    "parent": "/products",
                    "active": "0",
                    "label": "Test",
                    "route": "/test"
                }
            ]
        }
    ]
    },
    {
        "parent": "root",
        "active": "1",
        "label": "404",
        "route": "/404"
    },
    {
        "parent": "root",
        "active": "1",
        "label": "Login",
        "route": "/login"
    }
]

I am having major trouble returning from a function the following structure:

[
{
    "parent": "root",
    "active": "1",
    "label": "Index",
    "route": "/"
},
{
    "parent": "/products",
    "active": "0",
    "label": "Test",
    "route": "/test"
},
{
    "parent": "/",
    "active": "1",
    "label": "Products",
    "route": "/products"
},
{
    "parent": "root",
    "active": "1",
    "label": "404",
    "route": "/404"
},
{
    "parent": "root",
    "active": "1",
    "label": "Login",
    "route": "/login"
}
]

Essentially I want to recurse through all the children and populate a new array with every parent and child in the nested arrays, I have tried array_merge, RecursiveIteratorIterator, iterator_to_array, array_map, but it always comes unstuck on the recursion. I managed to do it when the children were only one level deep but two or more simply breaks down.

VeeeneX : Yes, they don't give me the results I desire, they ony return the parents and not the children. — user3169851, Feb 08 '15 at 12:07

georg · Answer 1 · 2015-02-08T15:49:58.057

4

Easy-peasy

function flatten($items, &$r) {
    foreach($items as $item) {
        $c = isset($item->children) ? $item->children : null;
        unset($item->children);
        $r []= $item;
        if($c)
            flatten($c, $r);
    }
}

flatten(json_decode($json), $r);
print_r($r);

This accumulates results in one single buffer, passed by reference. This is far more efficient than building a whole new array on each iteration, which is basically a variation of the Shlemiel the painter's algorithm.

If you prefer functional approach, you can use generators:

function flatten($items) {
    foreach($items as $item) {
        $c = isset($item->children) ? $item->children : [];
        unset($item->children);
        yield $item;
        foreach(flatten($c) as $child)
            yield $child;
    }
}

foreach(flatten(json_decode($json)) as $item)
    print_r($item);

edited Feb 08 '15 at 15:49

answered Feb 08 '15 at 12:04

georg

211,518
52
313
390

I'll certainly agree that my algorithm is much more "wasteful". I simply do prefer the functional approach and notation over pass-result-as-argument-by-reference. It'd have to be a proven bottleneck for me to rewrite it your way. +1 nonetheless :) – deceze Feb 08 '15 at 13:41
Are these functions easily reversible? For example taking the output structure of these and turning them back into my original json? – user3169851 Feb 09 '15 at 14:02
@user3169851: yes, iterate over the flat result and add the current item to `$tree[$item->parent]->children`. – georg Feb 09 '15 at 14:07

score 2 · Accepted Answer · answered Feb 08 '15 at 12:04

2

Not very hard:

function flatten(array $array) {
    $branch = [];

    foreach ($array as $item) {
        $children = [];
        if (isset($item['children']) && is_array($item['children'])) {
            $children = flatten($item['children']);
            unset($item['children']);
        }
        $branch = array_merge($branch, [$item], $children);
    }

    return $branch;
}

answered Feb 08 '15 at 12:04

deceze

510,633
85
743
889

This answer would be more helpful with an educational explanation. – mickmackusa Sep 12 '22 at 05:14

Flatten an array with parent-child relationships so that all children are on the parent level

2 Answers2

Linked