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?

Solution 1

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

Solution 2

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

Solution 3

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

Solution 4

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

Solution 5

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

View more solutions

Comments

[acm]

didn't get it... your list is a PHP array?

[GWW]

possible duplicate of How can I convert a series of parent-child relationships into a hierarchical tree?

[Gordon]

@andre OP is looking for an adjacency list. There is a number of duplicates for this.

[erisco]

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?

[Thunderstriker]

sry typo in array but it was indeed array of arrays edited it now

[Admin]

Possible duplicate of Convert a series of parent-child relationships into a hierarchical tree?

[Ilya Kolesnikov]

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: bitworks.software/en/2017-10-20-storing-trees-in-rdbms.html

[erisco]

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.

[DampeS8N]

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.

[erisco]

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.

[Thunderstriker]

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

[Adam]

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

[mike_hornbeck]

Any ideas how to get this one working with any parentId on the lowest level ? stackoverflow.com/questions/11942115/…

[Peter Krauss]

Good way, faster than recurrence! Needs a little fix, "Notice: Undefined index: father"

[Marco Panichi]

@PeterKrauss I've fixed the notice (and also improve a little bit the formatting)

[Altenrion]

Found this solusion, helped a lot!

[Jin]

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?

[srayner]

I liked this example so I wrapped it in a class and made it available on github here; github.com/srayner/NavTree

[Oleg Abrazhaev]

what if we will have a loop here?

[472084]

@JinIzzraeel If you want to pass non-objects by ref, you need the ampersand. Recursion is not discouraged in PHP.

[Happy Coder]

How to add an element to this tree as a child of a particular parent?

[Vasily]

@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

[Disorder]

man you saved me from pulling out my hair today. thanks a lot.

[Admin]

personally, I'd make $array immutable and just add parentless items to a new array then return that array.

[Alan Delval]

It works perfectly with multiple root parents with id 0.

[seniorpreacher]

Based on @Vasily 's answer, I made an "array of instances" tree builder: gist.github.com/seniorpreacher/64adfcf4844974b568bc84bf3056c‌​05e

[Sithell]

What is idKey? My ide keeps complaining about it

[Vasily]

@Sithell, that was an extra unused variable, deleted it, thanks!