Creating a tiered array using parentIds in PHP

Question

I am trying to customize a list that can have multiple levels using parentId to determine its parent. The first element of parentId is NULL. An example of some entries:

 id parentId name 1 NULL item1 2 NULL item2 3 1 item3 4 2 item4 5 3 item5 6 3 item6 

So, 1 and 2 are the main points; 3 - child 1; 4 - child 2; 5 is a child of 3 (who is a child of one of them); 6 is also a child of 3 (who is a child of one of them); and etc.

I am stuck in creating an array that correctly adds these elements to the right levels. It should look like this:

 Array ( [1] => Array ( [name] => item1 [parentId] => [children] => Array ( [3] => Array ( [name] => item3 [parentId] => 1 [children] => Array ( [5] => Array ( [name] => item5 [parentId] => 3 ) [6] => Array ( [name] => item6 [parentId] => 3 ) ) ) ) ) [2] => Array ( [name] => item2 [parentId] => [children] => Array ( [4] => Array ( [name] => item4 [parentId] => 2 ) ) ) ) 

But I will say that I look through all the elements using foreach() , and I get the element 5. Its parentId is 3, but at this moment I have no idea where this parent element 3 is in the array, and how to add children to this parent .

Is there a trick to iterate over these elements and put them in place correctly?

Answer 1

Here

 // your original data as an array $data = array( array( 'id' => 1, 'parentId' => null, 'name' => 'item1' ), array( 'id' => 2, 'parentId' => null, 'name' => 'item2' ), array( 'id' => 3, 'parentId' => 1, 'name' => 'item3' ), array( 'id' => 4, 'parentId' => 2, 'name' => 'item4' ), array( 'id' => 5, 'parentId' => 3, 'name' => 'item5' ), array( 'id' => 6, 'parentId' => 3, 'name' => 'item6' ), ); 

Recursive function

 function buildTree( $ar, $pid = null ) { $op = array(); foreach( $ar as $item ) { if( $item['parentId'] == $pid ) { $op[$item['id']] = array( 'name' => $item['name'], 'parentId' => $item['parentId'] ); // using recursion $children = buildTree( $ar, $item['id'] ); if( $children ) { $op[$item['id']]['children'] = $children; } } } return $op; } print_r( buildTree( $data ) ); /* Array ( [1] => Array ( [name] => item1 [parentId] => [children] => Array ( [3] => Array ( [name] => item3 [parentId] => 1 [children] => Array ( [5] => Array ( [name] => item5 [parentId] => 3 ) [6] => Array ( [name] => item6 [parentId] => 3 ) ) ) ) ) [2] => Array ( [name] => item2 [parentId] => [children] => Array ( [4] => Array ( [name] => item4 [parentId] => 2 ) ) ) ) */ 

Answer 2

You should use the element identifier as the key value for the array, so you can add the parent element to it as follows:

 $array[$parentID]['children'][$childID] = array(); 

Answer 3

The first thing that comes to mind is just a flat version of what you have:

 array ( [0] => array( 'name' => 'item1', 'parent' => null ), [1] => array( 'name' => 'item2', 'parent' => null ), [3] => array( 'name' => 'item3', 'parent' => 0 ), [4] => array( 'name' => 'item4', 'parent' => 3 ), [5] => array( 'name' => 'item5', 'parent' => 1 ), [6] => array( 'name' => 'item6', 'parent' => 1 ), ); 

Basically, you are only referring to the parent. To find all the children, you have to iterate over the array. However, the initial setup time would be pretty quick.

The second that comes to mind, and will include much more settings, but much less access time:

 array ( [0] => array( 'name' => 'item1', 'parent' => null, 'children' = array(3) ), [1] => array( 'name' => 'item2', 'parent' => null 'children' = array(5, 6) ), [3] => array( 'name' => 'item3', 'parent' => 0 'children' = array(4) ), [4] => array( 'name' => 'item4', 'parent' => 3 'children' = array() ), [5] => array( 'name' => 'item5', 'parent' => 1 'children' = array() ), [6] => array( 'name' => 'item6', 'parent' => 1 'children' = array() ), ); 

In this, you add all the child indexes to the parent. This will take a little longer, but subsequent access times will be fast. When you figure out the parents, you simply add an array of parent children.

The only real drawback of the second approach is that if you want to add or remove an element, you need to remember to return and update the children array for the parent.

Answer 4

You may not need a new solution, but other users may find it useful:

 // ! assuming $elements is built like: Array( id1 => Array(/*parameters*/) , ...) function buildTree($elements) { $e = Array(0 => Array()); // elements array $r = Array(0 =>& Array()); // reference array while ($elements) {// repeat till $elements is empty // loop through (remaining) elements foreach ($elements as $id => $element) { $pid = $element['parentId']; // shortcut if (array_key_exists($pid,$r)) { // parent already parsed -> can add this element // use parent reference to elements array to add this element ( $r[$pid] =& $e[path][to][$pid] ) $r[$pid] ['elements'][$id] = $element; // create reference for this element using parent reference $r[$id] =& $r[$pid]['elements'][$id]; // unset current element in input array in order to limit while-loop unset($elements[$id]); } } } return $e; // or whatever you need, the reference array can be useful if you need to fetch an element only knowing its id } 

What does he do:

• declare an array for the results ( $e ) and add the root element ( 0/null )
• declare an array for links ( $r ) and already refer $r[0] to $e[0]
• through the input array until it is empty
  • make for each item:
  • check if the parent is being processed, if so, you know where this element belongs, and you can add it
    (this prevents me from getting it to work the first couple attempts and why the while needed).
  • add the current item using the parent link (note the & after = !)
  • create a new link using the parent link
  • disconnect the current element from the input array
    (you can leave this if you want endless while loops;))
• of cource return what you need!

The advantages of this method are as follows:

• you reduce the number of foreach loops (you assign the maximum possible value from what you currently know)
• each cycle gets shorter because you disabled the parsed elements in the input array ( $elements )
• you can also return a reference array and be able to quickly get the parameters of an element, provided that you know its id

In other words: it should be faster (I have not tested it!), At least for more complex tasks, such as the one I use for it.