create array tree from array list

Question

i have a list like this:

array(
  array(id=>100, parentid=>0, name=>'a'),
  array(id=>101, parentid=>100, name=>'a'),
  array(id=>102, parentid=>101, name=>'a'),
  array(id=>103, parentid=>101, name=>'a'),
)

but way bigger so i need a efficient way to make this into a tree like structure like this:

array(
  id=>100, parentid=>0, name=>'a', children=>array(
    id=>101, parentid=>100, name=>'a', children=>array(
      id=>102, parentid=>101, name=>'a',
      id=>103, parentid=>101, name=>'a',
    )
  )
)

i cannot use things like nested set or things like that becoas i can add left and right values in my database. any ideas?

@andre OP is looking for an adjacency list. There is a number of duplicates for this. — Gordon, Nov 16 '10 at 16:11
The arrays you have demoed do not make sense because you have duplicate keys. Did you mean to have an array of arrays or are you showing the implied meaning based on the index value? — erisco, Nov 16 '10 at 17:02
sry typo in array but it was indeed array of arrays edited it now — Thunderstriker, Nov 16 '10 at 17:11
This flat array list is one of kinds of tree store in relational database and is named Adjacency list. There are another ways to store tree in RDBMS which are described in articles like this: https://bitworks.software/en/2017-10-20-storing-trees-in-rdbms.html — Ilya Kolesnikov, May 30 '21 at 06:16

score 65 · Accepted Answer · answered Nov 16 '10 at 17:10

65

oke this is how i solved it:

$arr = array(
  array('id'=>100, 'parentid'=>0, 'name'=>'a'),
  array('id'=>101, 'parentid'=>100, 'name'=>'a'),
  array('id'=>102, 'parentid'=>101, 'name'=>'a'),
  array('id'=>103, 'parentid'=>101, 'name'=>'a'),
);

$new = array();
foreach ($arr as $a){
    $new[$a['parentid']][] = $a;
}
$tree = createTree($new, array($arr[0]));
print_r($tree);

function createTree(&$list, $parent){
    $tree = array();
    foreach ($parent as $k=>$l){
        if(isset($list[$l['id']])){
            $l['children'] = createTree($list, $list[$l['id']]);
        }
        $tree[] = $l;
    } 
    return $tree;
}

answered Nov 16 '10 at 17:10

Thunderstriker

1,279
1
11
11

2

This works well, just make sure that, if you have more than one item with parentid=0, to loop through all the items and check for parentid == 0. If that's true, then run createTree on that item and append it to your tree array. Otherwise, this routine only works for the first item where parentid=0 – Adam Apr 12 '11 at 21:26
Found this solusion, helped a lot! – Altenrion Jun 29 '16 at 21:19
Question: Is the &$list required or can it also work with $list? I believe that's what PHP uses to pass by ref. Also, is recursion discouraged in PHP? – Jin Nov 22 '16 at 15:08
2

@JinIzzraeel If you want to pass non-objects by ref, you need the ampersand. Recursion is not discouraged in PHP. – 472084 Apr 12 '17 at 09:17
man you saved me from pulling out my hair today. thanks a lot. – Disorder Mar 27 '18 at 10:08

score 47 · Answer 2 · answered Apr 26 '12 at 11:20

small fix if you need more than 1 parentid[0] element :)

$arr = array(
  array('id'=>100, 'parentid'=>0, 'name'=>'a'),
  array('id'=>101, 'parentid'=>100, 'name'=>'a'),
  array('id'=>102, 'parentid'=>101, 'name'=>'a'),
  array('id'=>103, 'parentid'=>101, 'name'=>'a'),
);

$new = array();
foreach ($arr as $a){
    $new[$a['parentid']][] = $a;
}
$tree = createTree($new, $new[0]); // changed
print_r($tree);

function createTree(&$list, $parent){
    $tree = array();
    foreach ($parent as $k=>$l){
        if(isset($list[$l['id']])){
            $l['children'] = createTree($list, $list[$l['id']]);
        }
        $tree[] = $l;
    } 
    return $tree;
}

Any ideas how to get this one working with any parentId on the lowest level ? http://stackoverflow.com/questions/11942115/convert-flat-array-to-nested-parent-child-structure#comment15908756_11942115 — mike_hornbeck, Aug 15 '12 at 06:36

Vasily · Answer 3 · 2021-03-30T19:04:45.440

23

One more rework of Thunderstriker's variant - all the logic in one function:

/**
 * @param array $flatList - a flat list of tree nodes; a node is an array with keys: id, parentID, name.
 */
function buildTree(array $flatList)
{
    $grouped = [];
    foreach ($flatList as $node){
        $grouped[$node['parentID']][] = $node;
    }

    $fnBuilder = function($siblings) use (&$fnBuilder, $grouped) {
        foreach ($siblings as $k => $sibling) {
            $id = $sibling['id'];
            if(isset($grouped[$id])) {
                $sibling['children'] = $fnBuilder($grouped[$id]);
            }
            $siblings[$k] = $sibling;
        }
        return $siblings;
    };

    return $fnBuilder($grouped[0]);
}

// Example:
$flat = [
    ['id' => 100, 'parentID' => 0, 'name' => 'root'],
    ['id' => 101, 'parentID' => 100, 'name' => 'ch-1'],
    ['id' => 102, 'parentID' => 101, 'name' => 'ch-1-1'],
    ['id' => 103, 'parentID' => 101, 'name' => 'ch-1-2'],
];

$tree = buildTree($flat, 'parentID', 'id');
echo json_encode($tree, JSON_PRETTY_PRINT);

Playground: https://www.tehplayground.com/Ap4uUuwHWl9eiJIx

edited Mar 30 '21 at 19:04

answered Dec 08 '14 at 14:53

Vasily

1,858
1
21
34

3

I liked this example so I wrapped it in a class and made it available on github here; https://github.com/srayner/NavTree – srayner Jan 23 '17 at 21:27
How to add an element to this tree as a child of a particular parent? – Happy Coder Sep 26 '17 at 17:20
@HappyCoder just add an element to the $flat, for example `['id'=>103, 'parentID'=>101, 'name'=>'a']` - it's a child of a `['id'=>101, 'parentID'=>100, 'name'=>'a']` element – Vasily Sep 26 '17 at 17:32
Based on @Vasily 's answer, I made an "array of instances" tree builder: https://gist.github.com/seniorpreacher/64adfcf4844974b568bc84bf3056c05e – seniorpreacher Sep 17 '19 at 09:42
What is idKey? My ide keeps complaining about it – Sithell Mar 28 '21 at 01:49
@Sithell, that was an extra unused variable, deleted it, thanks! – Vasily Mar 30 '21 at 19:06

score 14 · Answer 4 · edited May 23 '17 at 12:34

Here is my adaptation from arthur's rework:

/* Recursive branch extrusion */
function createBranch(&$parents, $children) {
    $tree = array();
    foreach ($children as $child) {
        if (isset($parents[$child['id']])) {
            $child['children'] =
                $this->createBranch($parents, $parents[$child['id']]);
        }
        $tree[] = $child;
    } 
    return $tree;
}

/* Initialization */
function createTree($flat, $root = 0) {
    $parents = array();
    foreach ($flat as $a) {
        $parents[$a['parent']][] = $a;
    }
    return $this->createBranch($parents, $parents[$root]);
}

Use:

$tree = createTree($flat);

It works perfectly with multiple root parents with id 0. – Alan Delval Mar 17 '19 at 05:40 — Alan Delval, Mar 17 '19 at 05:40

Marco Panichi · Answer 5 · 2015-10-19T15:14:11.560

I created an unusual ('while-based' instead of recursive) but multidimensional sorting function that walk the array until there aren't any orphans. Here the function:

function treeze( &$a, $parent_key, $children_key )
{
    $orphans = true; $i;
    while( $orphans )
    {
        $orphans = false;
        foreach( $a as $k=>$v )
        {
            // is there $a[$k] sons?
            $sons = false;
            foreach( $a as $x=>$y )
            if( isset($y[$parent_key]) and $y[$parent_key]!=false and $y[$parent_key]==$k )  
            { 
                $sons=true; 
                $orphans=true; 
                break;
            }

            // $a[$k] is a son, without children, so i can move it
            if( !$sons and isset($v[$parent_key]) and $v[$parent_key]!=false )
            {
                $a[$v[$parent_key]][$children_key][$k] = $v;
                unset( $a[$k] );
            }
        }
    }
}

Recommendation: the key of each element of the array has to be the id fo the element itself. Example:

$ARRAY = array(
    1 => array( 'label' => "A" ),
    2 => array( 'label' => "B" ),
    3 => array( 'label' => "C" ),
    4 => array( 'label' => "D" ),
    5 => array( 'label' => "one", 'father' => '1' ),
    6 => array( 'label' => "two", 'father' => '1' ),
    7 => array( 'label' => "three", 'father' => '1' ),
    8 => array( 'label' => "node 1", 'father' => '2' ),
    9 => array( 'label' => "node 2", 'father' => '2' ),
    10 => array( 'label' => "node 3", 'father' => '2' ),
    11 => array( 'label' => "I", 'father' => '9' ),
    12 => array( 'label' => "II", 'father' => '9' ),
    13 => array( 'label' => "III", 'father' => '9' ),
    14 => array( 'label' => "IV", 'father' => '9' ),
    15 => array( 'label' => "V", 'father' => '9' ),
);

Usage: the function need $a (the array), $parent_key (the name of the column where the id of the father is saved), $children_key (the name of the column where the children will be move). It returns nothing (the array is changed by reference). Example:

treeze( $ARRAY, 'father', 'children' );
echo "<pre>"; print_r( $ARRAY );

Good way, faster than recurrence! Needs a little fix, "Notice: Undefined index: father" — Peter Krauss, Jan 09 '14 at 07:50
@PeterKrauss I've fixed the notice (and also improve a little bit the formatting) — Marco Panichi, Oct 19 '15 at 15:16

score 3 · Answer 6 · edited Jun 19 '16 at 21:52

//if order by parentid, id
$arr = array(
    array('id'=>100, 'parentid'=>0, 'name'=>'a'),
    array('id'=>101, 'parentid'=>100, 'name'=>'a'),
    array('id'=>102, 'parentid'=>101, 'name'=>'a'),
    array('id'=>103, 'parentid'=>101, 'name'=>'a'),
);

$arr_tree = array();
$arr_tmp = array();

foreach ($arr as $item) {
    $parentid = $item['parentid'];
    $id = $item['id'];

    if ($parentid  == 0)
    {
        $arr_tree[$id] = $item;
        $arr_tmp[$id] = &$arr_tree[$id];
    }
    else 
    {
        if (!empty($arr_tmp[$parentid])) 
        {
            $arr_tmp[$parentid]['children'][$id] = $item;
            $arr_tmp[$id] = &$arr_tmp[$parentid]['children'][$id];
        }
    }
}

unset($arr_tmp);
echo '<pre>'; print_r($arr_tree); echo "</pre>";

score 1 · Answer 7 · edited Sep 17 '18 at 08:35

Is there any reason this three pass method wouldn't work? I didn't do any tests to compare speed to some of the recursive solutions, but it seemed more straight forward. If your initial array is already associative with the IDs being the key, then you can skip the first foreach().

function array_tree(&$array) {
    $tree = array();

    // Create an associative array with each key being the ID of the item
    foreach($array as $k => &$v) {
      $tree[$v['id']] = &$v;
    }

    // Loop over the array and add each child to their parent
    foreach($tree as $k => &$v) {
        if(!$v['parent']) {
          continue;
        }
        $tree[$v['parent']]['children'][] = &$v;
    }

    // Loop over the array again and remove any items that don't have a parent of 0;
    foreach($tree as $k => &$v) {
      if(!$v['parent']) {
        continue;
      }
      unset($tree[$k]);
    }

    return $tree;
}

personally, I'd make `$array` immutable and just add parentless items to a new array then return that array. — , Sep 17 '18 at 08:40

score 1 · Answer 8 · answered Nov 16 '10 at 16:16

1

One way to do this is with a recursive function that first finds all the bottom values of the list, adding them to a new array. Then for each new id, you use the same function on that id, taking the returned array and stuffing it in that item's new children array. Finally, you return your new array.

I won't do all the work for you, but the function's parameters will look something like:

function recursiveChildren($items_array, $parent_id = 0)

Essentially, it'll find all the ones with parent of 0, then for each of those it'll find all the ones with that id as the parent, and for each of those.. so on.

The end result should be what you are looking for.

answered Nov 16 '10 at 16:16

DampeS8N

3,621
17
20

The problem with this algorithm is that it is likely O(n^2). Consider an array where every element is the parent of the next. This algorithm would scan the array n times, resulting in n(n+1)/2 operations. – erisco Nov 16 '10 at 16:50
So remove the items from the old array as you find them before passing it along. My intention here was just to get a sketch of a function that will do the job. Not do the job fast. That's for optimization later on. This is the web. Caching is a better place to expend these kinds of mental energies. – DampeS8N Nov 16 '10 at 16:55
My calculation of n(n+1)/2 operations accounted for the fact that the array is shrinking after every scan. The OP stated that his data structure was "way bigger"; I feel it is implied that O(n^2) is too expensive. – erisco Nov 16 '10 at 16:58
i was doing it like this until my tree where becomming to big that is way i asked for an efficient way it to mo about 1 second to create the tree and had to load several of them so this solution is to slow. i posted my solution this ony will do it in 5ms – Thunderstriker Nov 17 '10 at 06:37

score 1 · Answer 9 · answered Jan 16 '21 at 11:06

A simpler version:

function build_tree(&$items, $parentId = null) {
    $treeItems = [];
    foreach ($items as $idx => $item) {
        if((empty($parentId) && empty($item['parent_id'])) || (!empty($item['parent_id']) && !empty($parentId) && $item['parent_id'] == $parentId)) {
            $items[$idx]['children'] = build_tree($items, $items[$idx]['id']);
            $treeItems []= $items[$idx];
        }
    }

    return $treeItems;
}
build_tree($array);

create array tree from array list

9 Answers9

Linked

Related