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;
    }
Improve this question
8
  • 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? Commented Jan 12, 2012 at 18:30
  • Yeah... what is the question here? Commented Jan 12, 2012 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. Commented Jan 12, 2012 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? Commented Jan 12, 2012 at 18:35
  • Read this article sitepoint.com/hierarchical-data-database I hope it will be helpful for you Commented Jan 12, 2012 at 18:38

14 Answers 14

Reset to default
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;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

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: stackoverflow.com/questions/4196157/… (Arthur's modified solution)
It doesn't save first parents without children.
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); ..."
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.
fix the issue @danicotra points out with the following: foreach ($elements as $i => $element) and unset($elements[$i]);
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;
}
Improve this answer

2 Comments

Nice solution, works great with wp_get_nav_menu_items, which gives a lot of freedom on creating custom menus with wordpress. wow!
If you want tree without keys (just with indexes 0,1,2,...) change the line $branch[$element['id']] = $element; to $branch[] = $element;
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);
Improve this answer

Comments

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.

Improve this answer

1 Comment

+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.
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
Improve this answer

Comments

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.

Improve this answer

Comments

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;
}
Improve this answer

1 Comment

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.
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/

Improve this answer

2 Comments

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 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 :)
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;
}
Improve this answer

Comments

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.

Improve this answer

Comments

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);
        }
    }
}
Improve this answer

Comments

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));
Improve this answer

Comments

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];
    }
}
Improve this answer

Comments

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;
        }
    }
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.