55

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;
    }
DSkinner
  • 593
  • 1
  • 4
  • 7
  • 1
    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? – MetalFrog Jan 12 '12 at 18:30
  • Yeah... what is the question here? – Wes Crow Jan 12 '12 at 18:32
  • 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. – DSkinner Jan 12 '12 at 18:33
  • 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? – Daniel West Jan 12 '12 at 18:35
  • 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. – Umbrella Jan 12 '12 at 18:43
  • Read this article http://www.sitepoint.com/hierarchical-data-database I hope it will be helpful for you – Dipu Raj Jan 12 '12 at 18:38
  • 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: http://www.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). – Wrikken Jan 12 '12 at 18:49
  • The overview of relative costs in on slide 69 BTW. – Wrikken Jan 12 '12 at 18:56

14 Answers14

68

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;
}
Pierre de LESPINAY
  • 44,700
  • 57
  • 210
  • 307
n0nag0n
  • 1,575
  • 1
  • 17
  • 25
  • 3
    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: http://stackoverflow.com/questions/4196157/create-array-tree-from-array-list (Arthur's modified solution) – danicotra Mar 22 '13 at 20:22
  • 1
    It doesn't save first parents without children. – mrded Jan 06 '15 at 20:01
  • 2
    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); ..." – Pyetro Mar 10 '17 at 13:39
  • Time complexity of this is `O(n^2)` or `O(n log n)` with @Pyetro 's suggestion. Look at my answer for a linear solution. – Leo Nov 09 '20 at 13:07
  • fix the issue @danicotra points out with the following: `foreach ($elements as $i => $element)` and `unset($elements[$i]);` – farinspace Dec 16 '20 at 22:35
40

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;
}
SteveEdson
  • 2,485
  • 2
  • 28
  • 46
  • Nice solution, works great with wp_get_nav_menu_items, which gives a lot of freedom on creating custom menus with wordpress. wow! – klewis Jan 13 '19 at 20:59
  • If you want tree without keys (just with indexes 0,1,2,...) change the line `$branch[$element['id']] = $element;` to `$branch[] = $element;` – Petr Pánek Feb 03 '21 at 08:00
6

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);
Eugen Rieck
  • 64,175
  • 10
  • 70
  • 92
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.

Wrikken
  • 69,272
  • 8
  • 97
  • 136
  • +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. – bumerang May 06 '16 at 13:17
3

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.

Inglis Baderson
  • 779
  • 4
  • 12
3

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;
}
touzas
  • 89
  • 3
  • 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 @SteveEdson might work better. – Sjaak Wish Jun 04 '22 at 11:37
3

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
Community
  • 1
  • 1
Micromega
  • 12,486
  • 7
  • 35
  • 72
1

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;
}
Arne M
  • 87
  • 8
1

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.

Leo
  • 5,013
  • 1
  • 28
  • 65
1

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/

Daniel West
  • 1,808
  • 2
  • 24
  • 34
  • 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. – Wrikken Jan 12 '12 at 19:00
  • @Wrikken 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 :) – Daniel West Jan 12 '12 at 19:28
0

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);
        }
    }
}
Mamed Shahmaliyev
  • 177
  • 2
  • 3
0

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));
Ulrich-Lorenz Schlüter
  • 440
  • 6
  • 12
0

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];
    }
}
hoorider
  • 111
  • 4
0

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;
        }
    }
Akbarali
  • 688
  • 7
  • 16