Build a tree from a flat array in PHP [duplicate]

Question

I've looked around the internet and haven't quite found what I'm looking for. I have a flat array with each element containing an 'id' and a 'parent_id'. Each element will only have ONE parent, but may have multiple children. If the parent_id = 0, it is considered a root level item. I'm trying to get my flat array into a tree. The other samples I have found only only copy the element to the parent, but the original still exists.

EDIT

Each element of the starting array is read from a separate XML file. The file itself will have '0' as the value for parent_id if it doesn't have a parent. The keys are actually strings.

I'm sorry for the confusion earlier. Hopefully this is more clear:

/EDIT

My starting array:

Array
(
    [_319_] => Array
        (
            [id] => 0
            [parent_id] => 0
        )

    [_320_] => Array
        (
            [id] => _320_
            [parent_id] => 0
        )

    [_321_] => Array
        (
            [id] => _321_
            [parent_id] => _320_
        )

    [_322_] => Array
        (
            [id] => _322_
            [parent_id] => _321_
        )

    [_323_] => Array
        (
            [id] => _323_
            [parent_id] => 0
        )

    [_324_] => Array
        (
            [id] => _324_
            [parent_id] => _323_
        )

    [_325_] => Array
        (
            [id] => _325_
            [parent_id] => _320_
        )
)

The resulting array after the tree is made:

Array
(
    [_319_] => Array
        (
            [id] => _319_
            [parent_id] => 0
        )

    [_320_] => Array
        (
            [id] => _320_
            [parent_id] => 0
            [children] => Array
                (
                    [_321_] => Array
                        (
                            [id] => _321_
                            [parent_id] => _320_
                            [children] => Array
                                (
                                    [_322_] => Array
                                        (
                                            [id] => _322_
                                            [parent_id] => _321_
                                        )
                                )
                        )
                    [_325_] => Array
                        (
                            [id] => _325_
                            [parent_id] => _320_
                        )
                )
    [_323_] => Array
        (
            [id] => _323_
            [parent_id] => 0
            [children] => Array
                (
                    [_324_] => Array
                        (
                            [id] => _324_
                            [parent_id] => _323_
                        )
                )
        )

Any help / guidance is greatly appreciated!

Some code I have so far:

        function buildTree(array &$elements, $parentId = 0) {
        $branch = array();

        foreach ($elements as $element) {
            if ($element['parent_id'] == $parentId) {
                $children = $this->buildTree($elements, $element['id']);
                if ($children) {
                    $element['children'] = $children;
                }
                $branch[] = $element;
            }
        }

        return $branch;
    }

Livy

I'm confused. Are you just asking us to write the code that takes your fist array and spits out what you have in the second array? – Bookstack

Yeah... what is the question here? – Ohaus

In short, I guess so. I've looked at various other examples here on stackoverflow, and on other blogs/forums. But when I've tried them they don't work. – Livy

If you are creating that array to begin with why don't you sort it into a tree automatically by searching for the parent_id of an array? – Jook

Read this article sitepoint.com/hierarchical-data-database I hope it will be helpful for you – Sueannsuede

Don't forget to make sure your source array is sorted by parent_id ascending before building your tree to prevent a failure when a node's parent is not in the tree yet. – Mills

The adjacency model has a lot of advantages over nested set (which is very costly when altering a location). Bill's slideshow shows a handy overview of costs of different models: slideshare.net/billkarwin/models-for-hierarchical-data. Note that in PosgresSQL, Oracle, DB2 and MSSQL the adjacency list is a lot more viable then in MySQL (can't wait until those implement it). – Schulze

The overview of relative costs in on slide 69 BTW. – Schulze

Answer 1

You forgot the unset() in there bro.

function buildTree(array &$elements, $parentId = 0) {
    $branch = array();

    foreach ($elements as $element) {
        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$element['id']] = $element;
            unset($elements[$element['id']]);
        }
    }
    return $branch;
}

Gastight

This solution could fail building the tree correctly in certain circumstances (i.e. $arr = array( array('id'=>1, 'parentid'=>0), array('id'=>10, 'parentid'=>2), array('id'=>2, 'parentid'=>0), array('id'=>3, 'parentid'=>10), array('id'=>4, 'parentid'=>0), array('id'=>11, 'parentid'=>1), array('id'=>5, 'parentid'=>0), array('id'=>6, 'parentid'=>1), array('id'=>8, 'parentid'=>11), array('id'=>9, 'parentid'=>0), array('id'=>7, 'parentid'=>0), );) I'd suggest: #4196657 (Arthur's modified solution) – Quilmes

It doesn't save first parents without children. – Bickerstaff

You can get more performance in the search by adding this line of code: "array_splice($elements, $key, 1);" After this line: "if ($elmParent == $parentId) {" Staying like this: "... foreach ($elements as $key => $element) { if ($elmParent == $parentId) { array_splice($elements, $key, 1); ..." – Jus

Time complexity of this is O(n^2) or O(n log n) with @Jus 's suggestion. Look at my answer for a linear solution. – Publus

fix the issue @Quilmes points out with the following: foreach ($elements as $i => $element) and unset($elements[$i]); – Interurban

Answer 2

The solution by ImmortalFirefly is working, however, as mrded points out, it doesn't save first parents without children. I've edited the function to fix this issue:

function buildTree(array &$elements, $parentId = 0) {

    $branch = array();

    foreach ($elements as &$element) {

        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$element['id']] = $element;
            unset($element);
        }
    }
    return $branch;
}

Dissident

Nice solution, works great with wp_get_nav_menu_items, which gives a lot of freedom on creating custom menus with wordpress. wow! – Soppy

If you want tree without keys (just with indexes 0,1,2,...) change the line $branch[$element['id']] = $element; to $branch[] = $element; – Persaud

Answer 3

This works for me:

$index=array();
$tree=array();
foreach ($ori as $key=>$var) {
  $var=array_shift($ori);
  if ($var['id']==0) $var['id']=$key;
  if ((string)$var['parent_id']==='0') {
    $tree[$key]=$var;
    $index[$key]=&$tree[$key];
  } else if (isset($index[$var['parent_id']])) {
    if (!isset($index[$var['parent_id']]['children'])) $index[$var['parent_id']]['children']=array();
    $index[$var['parent_id']]['children'][$key]=$var;
    $index[$key]=&$index[$var['parent_id']]['children'][$key];
  } else {
    array_push($ori,$var);
  }
}
unset($index);
print_r($tree);

Burrstone

Answer 4

I can see the logic, save for this in the result:

Array
(
    [0] => Array
        (
            [id] => 0
            [parent_id] => 0
        )

    [1] => Array
        (
            [id] => 1
            [parent_id] => 0
        )

IMHO, is parent_id = o, shouldn't [1] be a child of [0] here?

Anyway, references to the rescue:

$tree = array();
foreach($inputarray as $item){
     if(!isset($tree[$item['id']])) $tree[$item['id']] = array();
     $tree[$item['id']] = array_merge($tree[$item['id']],$item);
     if(!isset($tree[$item['parent_id']])) $tree[$item['parent_id']] = array();
     if(!isset($tree[$item['parent_id']]['children'])) $tree[$item['parent_id']]['children'] = array();
     $tree[$item['parent_id']]['children'][] = &$tree[$item['id']];
}
$result = $tree[0]['children'];
unset($tree);
print_r($result);

Because you have abused 0 as both a 'magic' number as root, and an existing id, we now have recursion in the id=0 branch. Adding if($item['parent_id']!=$item['id']) before $tree[$item['parent_id']]['children'][] = &$tree[$item['id']]; could prevent that, but it isn't pretty.

Schulze

+1 becouse recusion has made allowed memory size exhausted in my case. In my case there was 54 objects and this was enought to fulfil my memory. – Syrinx

Answer 5

It's possible to construct the source array slightly different you can use this function(parent_id,id,title):

$q = mysql_query("SELECT id, parent_id, name FROM categories");
while ($r = mysql_fetch_row($q)) {
  $names[$r[0]] = $r[2];
  $children[$r[0]][] = $r[1];
 }

function render_select($root=0, $level=-1) {
  global $names, $children;
  if ($root != 0)
    echo '<option>' . strrep(' ', $level) . $names[$root] . '</option>';
  foreach ($children[$root] as $child)
    render_select($child, $level+1);
}

echo '<select>';
render_select();
echo '</select>';

1. More efficient hierarchy system

Useful

Answer 6

Though this is an old question, I'm gonna post my answer here:

/* assuming top level pid = 0 */
$rows = array (
    array ( 'id' => 1, 'pid' => 0 ),
    /* ... */
);

/* make id become array key */
$rows = array_column ( $rows, null, 'id' ); 

foreach ( $rows as $key => $val ) {
    if ( $val ['pid'] ) {
        if ( isset ( $rows [$val ['pid']] )) {
            $rows [$val ['pid']]['children'][] = &$rows [$key];
        }
    }
}

foreach ( $rows as $key => $val ) {
    if ( $val ['pid'] ) unset ( $rows [$key] );
}

array_column is PHP 5.5 but you can make your own easily.

Spathe

Answer 7

This is my solution, copy and optimize others solutions.

function buildTree(array &$elements, $parentId = 0) {
    $branch = array();
    foreach ($elements as $key => $element) {
        if ($element['parent_id'] == $parentId) {
            $children = $this->buildTree($elements, $key);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$key] = $element;
            unset($elements[$key]);
        }
    }
    return $branch;
}

Halm

Please note this answer uses an indexed array as key (0,1,2..). Which might work best with most results parsed from the database. In case you have your element id as key for the elements array the solution of @Dissident might work better. – Timmerman

Answer 8

You want to be looking at storing and loading hierarchical data in MySQL as I this should solve a few problems. I'm assuming that the first array represents data taken directly from the database?

It looks like you're trying to use the adjacency model to organize your data into the hierarchy structure. There are also other ways to achieve this using nesting. If you are not taking this data from a database then this may not be as useful.

This link should help you out: http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

Jook

Although it correctly illustrates the use of both the Adjacency Model as the Nested Set one, in practice (at least, in my experience), the Nested Set Model is waaaaay to costly on mutations (on average half your table needs to be updated!) for any practical data. If the data is relatively stale (i.e.: seldom changes) then it's viable, but usually, this isn't the case. – Schulze

@Schulze Yeah it depends on how the data is being used / updated. For categories it's fine but for data with a lot of modifications its not viable at all. Forgot to mention that, thanks :) – Jook

Answer 9

SteveEdson's code works fine, except in the case where the parent of an element does not exist in the original data structure. Here's my fix for that (however, it removes "parent_id" from elements, which may or may not be acceptable):

function buildTree(array &$elements, $parentId = 0)
{
    $branch = array();
    foreach ($elements as &$element) {
        if ($element["parent_id"] != null && $elements[$element["parent_id"]] == null)
            unset($element["parent_id"]);        
        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$element['id']] = $element;
            unset($element);
        }
    }
    return $branch;
}

Ignite

Answer 10

Here is my solution, which group items by parent_id first and then from the root recursively populates all the children branches using the grouped list for lookup.

public function get_nested_tree() {
    $parent_node = null;
    $nodes_by_parent = array();
    
    if(is_null($flat_list) || count($flat_list) <= 0){
        return null;
    }

    foreach ($flat_list as $node) {
        if($node['parent_id'] != null){
            $nodes_by_parent[$node['parent_id']][] = $node;
        }
        else{
            // NB. In my implementation if multiple roots exist,
            // I want to always return the first...
            if(is_null($parent_node)){
                $parent_node = $node;
            }
        }
    }

    return $this->populate_branch($parent_node, $nodes_by_parent);
}

public function populate_branch($node, $nodes_by_parent){
    $children = $nodes_by_parent[$node['id']] ?? [];

    foreach ($children as &$child){
        $child = $this->populate_branch($child, $nodes_by_parent);
    }

    $node['children'] = $children;

    return $node;
}

I believe the time complexity for this is linear (O(n)) - assuming that PHP associative arrays are equivalent to HashMap or Dictionary of other languages.

Publus

Answer 11

Here is my solution, works ideally, if we assume that the top level parent_id=0:

function MakeTree($arr){
    $parents_arr=array();
    foreach ($arr as $key => $value) {
        $parents_arr[$value['pid']][$value['id']]=$value;
    }
    $tree=$parents_arr['0'];
    $this->createTree($tree, $parents_arr);
    return $tree;
}
function createTree(&$tree, $parents_arr){
    foreach ($tree as $key => $value) {
        if(!isset($value['children'])) {
            $tree[$key]['children']=array();
        }
        if(array_key_exists($key, $parents_arr)){
            $tree[$key]['children']=$parents_arr[$key];
            $this->createTree($tree[$key]['children'], $parents_arr);
        }
    }
}

Imaginative

Answer 12

Clean, short and free of ballast. Array of arrays to tree:

class Mother {
    private $root;
    public function treeInit($array)
    {
        $this->root = new Child();
        foreach($array as $value){
            $this->root->treeClimb(array_reverse($value));
        }
        return $this->root;
    }
}

class Child {
    private $children = [];
    public function treeClimb($arr)
    {
        if(count($arr) > 0) {
            $childTmp = array_pop($arr);
            if(!key_exists($childTmp,$this->children))
            {
                $this->children[$childTmp] = new Child();
            }
        $this->children[$childTmp]->treeClimb($arr);
        }
    }
}

$array = array(array('obst','banae','krumm','gelb'),
                    array('obst','beere','him'),
                    array('obst','beere','brom'),
                    array('obst','banae','gerade'),
                    array('veg','carot','gerade'));

$obj = new Mother();
var_dump($obj->treeInit($array));

Rad

Answer 13

I came up with a similar solution as @eugen-rieck and wanted to share it. I named $branches my array of indices, though.

$tree = [];
$branches = [];

while (!empty($input)) {
    $beforeCount = count($input);

    foreach ($input as $id => $item) {
        $pid = $item['parent_id'];

        if (isset($branches[$pid])) {
            $branches[$pid]['children'][$id] = $item;
            $branches[$id] = &$branches[$pid]['children'][$id];
            unset($input[$id]);
        }
    }

    if ($beforeCount === count($input)) {
        $firstItem = array_shift($input);
        $id = $firstItem['id'];
        $tree[$id] = $firstItem;
        $branches[$id] = &$tree[$id];
    }
}

Sumac

Answer 14

In Laravel, this code helped me

<?php
    
    namespace App\Services;
    
    use App\Models\CategoryModel;
    
    class CategoryService
    {
        
        public function getTree(): array
        {
            $categories = CategoryModel::query()->orderBy('sort_category')
                ->select(['id', 'title', 'slug', 'image','parent_id'])
                ->get()->toArray();
            return $this->generateTree($categories);
        }
    
        public function generateTree($elements, $parentId = 0): array
        {
            $result = [];
            foreach ($elements as $element) {
                if ($element['parent_id'] == $parentId) {
                    $children = $this->generateTree($elements, $element['id']);
                    if ($children) {
                        $element['children'] = $children;
                    }
                    $result[$element['id']] = $element;
                    unset($elements[$element['id']]);
                }
            }
            return $result;
        }
    }

Skilful