Menu Building - Expanding Flat Data into a Tree

I had the opportunity this past weekend to help out a developer with a rather unique problem. He needed to ingest a flat datastructure but build a menu navigation system. He wasn't in control of the data structure and it was structured poorly. Below is an example of a recursion function that will take out-of-order "Nodes" and build a nested Array Tree.

Structure

$menu = [
    [
        'id' => 5,
        'pid' => 3,
        'name' => 'E'
    ],
    [
        'id' => 3,
        'pid' => 1,
        'name' => 'C'
    ],
    [
        'id' => 2,
        'pid' => 1,
        'name' => 'B'
    ],
    [
        'id' => 4,
        'pid' => 0,
        'name' => 'D'
    ],
    [
        'id' => 1,
        'pid' => 0,
        'name' => 'A'
    ],
];

//A
//  B
//  C
//    E
//D

The data looked something like this. The astute will note that this is not just a simple problem as the ordering of the menu nodes are ... not in order. Some googling around will show you a plethora of algorithms however many many of them will not solve the, "Out of Order Nodes" problem. Some further googling and inquiring will likely net you the, oh well just sort it first... When you have a rather large structure that's no easy task.

At the time I came up with a bit of a hacky solution, just to get the job done and make the client happy. This morning oddly enough I ran int the same problem myself. I needed to build a kind of "Blockchain" explorer for the billing system that I am writing (Life is funny like that I guess).

The code

function buildTree($flatStructure, $pidKey, $idKey = null)
{
    $parents = array();

    foreach ($flatStructure as $item){

        $parents[$item[$pidKey]][] = $item;
    }

    $fnBuilder = function($items, $parents, $idKey) use (&$fnBuilder) {

        foreach ($items as $position => $item) {

            $id = $item[$idKey];

            if(isset($parents[$id])) { //is the parent set
                $item['children'] = $fnBuilder($parents[$id], $parents, $idKey); //add children
            }

            //reset the value as children have changed
            $items[$position] = $item;
        }

        //return the item
        return $items;
    };

    return $fnBuilder($parents[0], $parents, $idKey);
}


$tree = buildTree($menu, 'pid', 'id');
print_r($tree);

I haven't fully completed everything but I figured that this is good enough for some people to toy around with. It could be further optimized by using a proper Object and avoding the currying of the function. But maybe that can be a version 2 thing.

When you run it you get a structure that looks like this!

Glenns-MacBook-Pro:glenneggleton$ php tree.php 
Array
(
    [0] => Array
        (
            [id] => 4
            [pid] => 0
            [name] => D
        )

    [1] => Array
        (
            [id] => 1
            [pid] => 0
            [name] => A
            [children] => Array
                (
                    [0] => Array
                        (
                            [id] => 3
                            [pid] => 1
                            [name] => C
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [id] => 5
                                            [pid] => 3
                                            [name] => E
                                        )

                                )

                        )

                    [1] => Array
                        (
                            [id] => 2
                            [pid] => 1
                            [name] => B
                        )

                )

        )

)

Hopefully this code can help you out!

Written by Glenn Eggleton on Monday October 23, 2017
Permalink - Chapter: php