Build a tree from a flat array in PHP

50
votes

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;
    }
13
phparraystreeflat
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
Yeah... what is the question here? – Wes Crow
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
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
Read this article sitepoint.com/hierarchical-data-database I hope it will be helpful for you – Dipu Raj

13 Answers

66
votes

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;
}
36
votes

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;
}
6
votes

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);
4
votes

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.

3
votes

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
2
votes

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.

1
votes

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/

1
votes

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;
}
0
votes

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);
        }
    }
}
0
votes

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;
}
0
votes

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));
0
votes

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];
    }
}
0
votes

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.