PHP build breadcrumb of tree array / flat array

Question

I'm strugling with building an array out of a product category array. This array is a tree array with parents and children. No I selecting one of the children, and I want to build the permalink towards this child.

I'm almost there, but somewhere I'm making a mistake and I can't figure it out.

So lets say I have this category array.

$cat = [
    0 => [
        "id" => "32",
        "shop_id" => "19",
        "parent_id" => "0",
        "name" => "T-shirts",
        "permalink" => "t-shirts",
        "image" => "category/image.jpg",
        "description" => "",
        "order" => "0",
        "children" => [
            0 => [
                "id" => "33",
                "shop_id" => "19",
                "parent_id" => "32",
                "name" => "Dames",
                "permalink" => "t-shirts/dames",
                "image" => "category/image.jpg",
                "description" => "",
                "order" => "0",
                "children" => [
                    0 => [
                        "id" => "38",
                        "shop_id" => "19",
                        "parent_id" => "33",
                        "name" => "V-hals",
                        "permalink" => "t-shirts/dames/v-hals",
                        "image" => "category/image.jpg",
                        "description" => "",
                        "order" => "0",
                        "children" => [
                            0 => [
                                "id" => "40",
                                "shop_id" => "19",
                                "parent_id" => "38",
                                "name" => "Rood",
                                "permalink" => "t-shirts/dames/v-hals/rood",
                                "image" => "",
                                "description" => "",
                                "order" => "0",
                                "children" => [
                                    0 => [
                                        "id" => "47",
                                        "shop_id" => "19",
                                        "parent_id" => "40",
                                        "name" => "Lange mouw",
                                        "permalink" => "t-shirts/dames/v-hals/rood/lange-mouw",
                                        "image" => "",
                                        "description" => "",
                                        "order" => "0",
                                        "children" => null,
                                    ]
                                ]
                            ]
                        ]
                    ]
                ]
            ]
        ]
    ]
];

Now I'm at category_id 38 and I want to build the breadcrumb. To accomplish that, I need the name of each category, and the permalink.

To accomplish that, I have flattend this array so they are all at the same level. At that point I'm using the following function:

function build_breadcrumb_from_category($categories, $pid)
{
    $return = [];
    foreach ($categories as $category) {
        if ($pid == $category['id']) {

            $return[] = [$category['name'], $category['permalink']];

            if ($category['parent_id'] > 0) {
                # Page has parents
                $return[] = build_breadcrumb_from_category($categories, $category['parent_id']);

            }

        }
    }
    return array_reverse($return);
}

But that gives me a kind of "tree" array again.

$breadcrumb = build_breadcrumb_from_category($flat_categories, 38);
$breadcrumb = [
    0 => [
        0 => [
            0 => [
                0 => [
                    0 => [
                        0 => "T-shirts",
                        1 => "t-shirts",
                    ],
                ],
                1 => [
                    0 => "Dames",
                    1 => "t-shirts/dames",
                ],
            ],
            1 => [
                0 => "V-hals",
                1 => "t-shirts/dames/v-hals",
            ]
        ],
        1 => [
            0 => "Rood",
            1 => "t-shirts/dames/v-hals/rood",
        ],
    ],
    1 => [
        0 => "Lange mouw",
        1 => "t-shirts/dames/v-hals/rood/lange-mouw",
    ],
];

I don't understand how I can get this array flat. How can I get a nice array, just one level deep where I can do a foreach.

Desired output

   $breadcrumbs = [
       [       
            0 => "T-shirts",
            1 => "t-shirts",
       ],
       [       
            0 => "Dames",
            1 => "t-shirts/dames",
       ],
       [       
            0 => "V-hals",
            1 => "t-shirts/dames/v-hals",
       ],
    ]

Answer 1

You could optimise this by indexing flattened array - too many search loops now (post your flattening function if you want better solution). The function you have doesn't need big changes though. You should build your parent structure first, push current position and then return it to higher scope (as its parent structure):

function build_breadcrumb_from_category($categories, $pid)
{
    $result = [];
    foreach ($categories as $category) {
        if ($pid == $category['id']) {
            if ($category['parent_id'] > 0) {
                # Page has parents
                $result = build_breadcrumb_from_category($categories, $category['parent_id']);
            }

            $result[] = [$category['name'], $category['permalink']];
        }
    }
    return $result;
}

Here's the solution with indexed category list - first function flattens the tree, second one uses its id indexes to build breadcrub path:

function category_index($category_tree)
{
    $result = [];
    foreach($category_tree as $category) {
        if (!empty($category['children'])) {
            $result = $result + category_index($category['children']);
        }
        unset($category['children']);
        $result[$category['id']] = $category;
    }
    return $result;
}

function category_breadcrumb($category_index, $pid)
{
    if (empty($category_index[$pid])) { return []; }

    $category = $category_index[$pid];
    $result   = ($category['parent_id']) ? category_breadcrumb($category_index, $category['parent_id']) : [];
    $result[] = [$category['name'], $category['permalink']];

    return $result;
}

Answer 2

My solution

function build_breadcrumb_from_category($categories, $pid)
{
    $result = [];
    foreach ($categories as $category)
    {
        if ($pid == $category['id'])
        {
            return [[$category['name'], $category['permalink']]];
        }

        $result = build_breadcrumb_from_category($category['children'], $pid);

        if (!empty($result))
        {   
            $result[] = [$category['name'], $category['permalink']];
            return $result;
        }       
    }    
}