PHP: Convert an array with a path attribute to a tree structure

Question

Lets say, I have the following array:

$array = array(
    array(
        "id"   => 1,
        "name" => "Europe",
        "path" => "/"
    ),
    array(
        "id"   => 2,
        "name" => "Germany",
        "path" => "/1/"
    ),
    array(
        "id"   => 3,
        "name" => "France",
        "path" => "/1/"
    ),
    array(
        "id"   => 4,
        "name" => "Berlin",
        "path" => "/1/2/"
    ),
    array(
        "id"   => 5,
        "name" => "Munich",
        "path" => "/1/2/"
    )
);

As you can see, its a multidimensional array with 3 properites in earch 2nd level array: id, name and path. The path is a path structure based on the parent-id of its parent. For example, Germany (id=2) has belongs to Europe, so the path is "/1/" (ID 1 = Europe) and Berlin in Germany has the path "/1/2/" which means "/Europe/Germany/"

Now, I am trying to create a tree-array out of this, which should somehow look like:

$result = array(
    1 => array(
        "id" => 1,
        "name" => "Europe",
        "path" => "/",
        "childs" => array(
            2 => array(
                "id" => 2,
                "name" => "Germany",
                "path" => "/1/",
                "childs" => array(
                    4 => array(
                        "id"   => 4,
                        "name" => "Berlin",
                        "path" => "/1/2/"
                    ),
                    5 => array(
                        "id"   => 5,
                        "name" => "Munich",
                        "path" => "/1/2/"
                    )
                )
            ),
            3 => array(
                "id"   => 3,
                "name" => "France",
                "path" => "/1/"
            )
        )
    )
);

I have already tried to create a function with internal references, but this didn't works for me:

public static function pathToTree($items) {
    $array = array();
    $result = array();

    foreach($items AS $res) {
        $ids = explode("/", ltrim($res["path"] . $res["id"], "/"));
        $count = count($ids);
        $tmp = &$result;

        foreach( $ids AS $id) {
            if($count == 1) {
                $tmp = $res;
                $tmp["childs"] = array();
                $tmp = &$tmp["childs"];
            }
            else {
                $tmp[$id] = array(
                    "childs" => array()
                );
                $tmp = &$tmp[$id]["childs"];
            }
            $count--;
        }
    }

    return $array;
}

means whenever we need to get inside and search for parents and childrens we use recursive functions because we dont know how deep level they will be. so we call a same function again and again till we reach where we want to and then return from there, thereby creating a pattern/hierarchy — Ashish Choudhary
– Ashish Choudhary, Commented Oct 22, 2015 at 18:34
I know what recursive means, but how can this help me with my problem? My base array has a defined depth of 2. — bernhardh
– bernhardh, Commented Oct 22, 2015 at 18:44
None of them would work if the the array containing Europe has the index other than the first one. — Muntashir Akon
– Muntashir Akon, Commented Oct 22, 2015 at 18:56

bernhardh · Accepted Answer · 2015-10-22 21:03:18Z

1

Ok, I think I just found a solution:

function pathToTree($array){
    $tree = array();
    foreach($array AS $item) {
        $pathIds = explode("/", ltrim($item["path"], "/") . $item["id"]);
        $current = &$tree;
        foreach($pathIds AS $id) {
            if(!isset($current["childs"][$id])) $current["childs"][$id] = array();
            $current = &$current["childs"][$id];
            if($id == $item["id"]) {
                $current = $item;
            }
        }
    }
    return $tree["childs"];
}

This is a dynamice solution for 1-n depth. Look at my example at http://ideone.com/gn0XLp . Here I tested it with some level:

Continent
Country
City
City-District
City-Subdistrict
City Sub-Sub-District

edited Oct 22, 2015 at 21:03

answered Oct 22, 2015 at 20:41

bernhardh

3,32911 gold badges46 silver badges79 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Muntashir Akon Over a year ago

Additionally, it depends on sequence. Sorry, I had a typo :(

bernhardh Over a year ago

You got a +1 for mentioning the sorting problem. But I do not have it in my situation, since the data is sorted by the database (ORDER BY path)

Muntashir Akon Over a year ago

Now I wonder more, why do you need to use this when you can easily manipulate data using SQL

bernhardh Over a year ago

In my database, I have a parent-child model for one table. I need this, to show the tree (for example in a ul-list). With SQL, I can easily find all children of a specific node (for example, to find ALL children of germany, I just have to query "WHERE path LIKE '/1/2/%' ORDER BY path". To find all parents of germany, I just have to query "WHERE id IN (" . explode("/", trim("/1/2/", "/")) . ")"

bernhardh Over a year ago

So I can query these things in ONE query, which wouldn't be possible with mysql with a simple "parent_id" system.

The fourth bird · Accepted Answer · 2015-10-23 01:44:40Z

I've created a recursive function:

// The array

$array = array(
    array(
        "id"   => 1,
        "name" => "Europe",
        "path" => "/"
    ),
    array(
        "id"   => 2,
        "name" => "Germany",
        "path" => "/1/"
    ),
    array(
        "id"   => 3,
        "name" => "France",
        "path" => "/1/"
    ),
    array(
        "id"   => 4,
        "name" => "Berlin",
        "path" => "/1/2/"
    ),
    array(
        "id"   => 5,
        "name" => "Munich",
        "path" => "/1/2/"
    ),
    array(
        "id"   => 6,
        "name" => "Asia",
        "path" => "/"
    ),
    array(
        "id"   => 7,
        "name" => "India",
        "path" => "/6/"
    ),
    array(
        "id"   => 7,
        "name" => "Mumbai",
        "path" => "/6/7"
    ),
    array(
        "id"   => 8,
        "name" => "Delhi",
        "path" => "/6/7"
    ),
);

// The recursive function

function createTree($input, &$result = array(), $key = null) {
    if ($key == "id") {
        $result["temp"]["id"] = $input;
    }
    if ($key == "name") {
        $result["temp"]["name"] = $input;
    }
    if ($key == "path") {
        $result["temp"]["path"] = $input;
        $levels = is_string($input) ? array_values(array_filter(explode('/', $input))) : null;
        if ($input == "/") {
            $result[$result["temp"]["id"]] = $result["temp"];
        }
        if (count($levels) == 1) {
            $result[$levels[0]]["childs"][$result["temp"]["id"]] = $result["temp"];
        }
        if (count($levels) == 2) {
            $result[$levels[0]]["childs"][$levels[1]]["childs"][$result["temp"]["id"]] = $result["temp"];
        }
        unset($result["temp"]);
    }
    if (is_array($input)) {
        foreach($input as $key => $value) {
            createTree($value, $result, $key);
        }
    }
    return $result;
}

// The result

array (
  1 => 
  array (
    'id' => 1,
    'name' => 'Europe',
    'path' => '/',
    'childs' => 
    array (
      2 => 
      array (
        'id' => 2,
        'name' => 'Germany',
        'path' => '/1/',
        'childs' => 
        array (
          4 => 
          array (
            'id' => 4,
            'name' => 'Berlin',
            'path' => '/1/2/',
          ),
          5 => 
          array (
            'id' => 5,
            'name' => 'Munich',
            'path' => '/1/2/',
          ),
        ),
      ),
      3 => 
      array (
        'id' => 3,
        'name' => 'France',
        'path' => '/1/',
      ),
    ),
  ),
  6 => 
  array (
    'id' => 6,
    'name' => 'Asia',
    'path' => '/',
    'childs' => 
    array (
      7 => 
      array (
        'id' => 7,
        'name' => 'India',
        'path' => '/6/',
        'childs' => 
        array (
          7 => 
          array (
            'id' => 7,
            'name' => 'Mumbai',
            'path' => '/6/7',
          ),
          8 => 
          array (
            'id' => 8,
            'name' => 'Delhi',
            'path' => '/6/7',
          ),
        ),
      ),
    ),
  ),
)

Muntashir Akon · Accepted Answer · 2015-10-22 20:06:10Z

As I said in the comment, you need at least three loops to achieve your goals. Here's the function:

function pathToTree($array){
    $tree = Array();
    for($i=0; $i < count($array); $i++){
        if(substr_count($array[$i]["path"], '/') == 1)
            $tree[$array[$i]["id"]] = $array[$i];
    }
    for($i=0; $i < count($array); $i++){
        if(substr_count($array[$i]["path"], '/') == 2){
            $num = (int)str_replace("/","",$array[$i]["path"]);
            $tree[$num]["childs"][$array[$i]["id"]] = $array[$i];
        }
    }
    for($i=0; $i < count($array); $i++){
        if(substr_count($array[$i]["path"], '/') == 3){
            $num = explode("/", $array[$i]["path"]);
            $tree[$num[1]]["childs"][$num[2]]["childs"][$array[$i]["id"]] = $array[$i];
        }
    }
    return $tree;
}

Example:

Consider this array:

$array = array(
    array(
        "id"   => 1,
        "name" => "Europe",
        "path" => "/"
    ),
    array(
        "id"   => 2,
        "name" => "Germany",
        "path" => "/1/"
    ),
    array(
        "id"   => 3,
        "name" => "France",
        "path" => "/1/"
    ),
    array(
        "id"   => 4,
        "name" => "Berlin",
        "path" => "/1/2/"
    ),
    array(
        "id"   => 5,
        "name" => "Munich",
        "path" => "/1/2/"
    ),
    array(
        "id"   => 6,
        "name" => "Asia",
        "path" => "/"
    ),
    array(
        "id"   => 7,
        "name" => "China",
        "path" => "/6/"
    ),
    array(
        "id"   => 8,
        "name" => "Bangladesh",
        "path" => "/6/"
    ),
    array(
        "id"   => 9,
        "name" => "Beijing",
        "path" => "/6/7/"
    ),
    array(
        "id"   => 10,
        "name" => "Dhaka",
        "path" => "/6/8/"
    )
);

if I ran this code:

print_r(pathToTree($array));

the output will be:

Here's the phpfiddle link in case you might try it yourself.

Sorry if I didn't made it clear enought, but: With depth of 2 I mean that the base array has only 2 levels $array = array(array(..), array(..)). The result can be of a depth of n (based on how deep the "path" is. So I can't just use 3 loops!
@leftjustified then you need n+1 loops! I am still trying to figure out if there are any other options. But I really wonder, why do you even need that!
Ok, I don't think that it's impossible. But may need some time. @leftjustified

Collectives™ on Stack Overflow

PHP: Convert an array with a path attribute to a tree structure

3 Answers 3

5 Comments

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related