Create a tree from a flat array

Question

I am having trouble in converting a flat array, e.g. from a DB query, into a tree structure. I have something like this:

[
  [ 
    id => 11,
    path => '/11',
    label => 'AAA'
  ],
  [ 
    id => 12,
    path => '/12',
    label => 'BBB'
  ],
  [ 
    id => 21,
    path => '/12/21',
    label => 'BBBB'
  ],
  [ 
    id => 21,
    path => '/12/22',
    label => 'CCCCC'
  ],
]

path points to the hierarchical position inside the tree, defined by the id's. So in the end I have to get something like this:

$tree=[
        [
            'id' => '11',
            'label' =>  'AAA'
        ],
        [
            'id' => '12',
            'label' =>  'BBB',
            'children' => [
                [
                    'id' => '21',
                    'label' =>  'BBBB'
                ],
                [
                    'id' => '22',
                    'label' =>  'CCCCC'
                ]
            ]
        ]
    ];

The depth can be infinite. I would appreciate any solution. Thank you :-)

I'm sorry, but why you want to do something awful like this? — André Walker
– André Walker, Commented Feb 12, 2021 at 16:48
supposing that is possible. when you are accessing a node with id '/x/y' you can guarantee that you already have accessed the node with id '/x'? — André Walker
– André Walker, Commented Feb 12, 2021 at 16:51
Could you maybe post the code you already have and where it fails? — user8034901
– user8034901, Commented Feb 12, 2021 at 16:55
@AndréWalker The structure to start with is from a Moodle insatnce, which organizes its categories this way. The objective structure is needed by a Vue component, which offers hierarchical select menues. So, I don't have any choice. — piccard
– piccard, Commented Feb 12, 2021 at 19:25
@AndréWalker At the beginning you have a flat structure, which you can sort in any way, for example you can sort the entries by the depth of the path. This way you can guarantee that you have already accessed 'x'. — piccard
– piccard, Commented Feb 12, 2021 at 19:32

piccard · Accepted Answer · 2021-02-13 16:34:46Z

Thank you all, but I am still stuck :-( Here's my way so far.

First I order the categories by depth & loop them in this order. This way I can be sure that the parent node exists.

    public function buildCategoryTree() {
        // order by depth
        $categoryLevel = [];
        foreach (Category::all() as $category) {
            $catPathSplitted = array_filter(explode("/", $category->path));
            $categoryLevel[count($catPathSplitted)][] = $category;
        }

        $categoryTree = [];

        // now loop each level and create a tree node
        foreach ($categoryLevel as $level => $categories) {
            foreach ($categories as $category) {
                $test = $category->path;
                $catPathSplitted = array_filter(explode("/", $category->path));
                $categoryTree = $this->addNode($category, $catPathSplitted, $categoryTree, $test);
            }
        }        
    }

Then I try to use this recursion, but it only works partially, means I get the child nodes in the hierarchical order, but the child nodes are also created again on each level. So there's something wrong :-(

    private function addNode($cat, $keys, &$tree) {
        foreach ($keys as $counter => $id) {
            if (!next($keys)) {
                if (!isset($tree[$id]['category'])) {
                    $tree[$id]['category'] = $cat->toArray();
                }
            } else {
                if (!isset($tree[$id]['children'])) {
                    $tree[$id]['children'] = [];
                }
                array_shift($keys);
                $this->addNode($cat, $keys, $tree[$id]['children'], $test);

            }
        }
        return $tree;
    }

Anybody can spot the flaw?

Got it :-) There was no recursion needed at all. Thank you for your hints.

Collectives™ on Stack Overflow

Create a tree from a flat array

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related