1

I have a problem that has been stressing me out for weeks now and i cannot find a clean solution to it that does not involve recursion.

This is the problem: Take a flat array of nested associative arrays and group this into one deeply nested object. The top level of this object will have its parent property as null.

This is my solution but i admit it is far from perfect. I am fairly certain this can be done in a single loop without any recursion, but for the life of me i cannot work it out!

//Example single fork
$data = array(

    //Top of Tree
    0 => array(
        "name" => "A",
        "parent" => null,
        "id" => 1,
    ),

    //B Branch
    1 => array(
        "name" => "B",
        "parent" => "1",
        "id" => 2,
    ),
    2 => array(
        "name" => "B1",
        "parent" => "2",
        "id" => 3,
    ),
    3 => array(
        "name" => "B2",
        "parent" => "3",
        "id" => 4,
    ),
    4 => array(
        "name" => "B3",
        "parent" => "4",
        "id" => 5,
    ),

    //C Branch
    5 => array(
        "name" => "C",
        "parent" => "1",
        "id" => 6,
    ),
    6 => array(
        "name" => "C1",
        "parent" => "6",
        "id" => 7,
    ),
    7 => array(
        "name" => "C2",
        "parent" => "7",
        "id" => 8,
    ),
    8 => array(
        "name" => "C3",
        "parent" => "8",
        "id" => 9,
    ),

);

Actual anonymised example
array:7214 [▼
  0 => array:3 [▼
    "name" => ""
    "parent" => null
    "id" => 
  ]
  1 => array:3 [▼
    "name" => ""
    "parent" => 
    "id" => 
  ]
  2 => array:3 [▼
    "name" => ""
    "parent" => 
    "id" => 
  ]
  3 => array:3 [▼
    "name" => ""
    "parent" => 
    "id" => 
  ]
  4 => array:3 [▼
    "name" => ""
    "parent" => 
    "id" => 
  ]
  5 => array:3 [▼
    "name" => ""
    "parent" => 
    "id" => 
  ]
  6 => array:3 [▼
    "name" => ""
    "parent" => 
    "id" => 
  ]
  7 => array:3 [▼
    "name" => ""
    "parent" => 
    "id" => 
  ]
  8 => array:3 [▼
    "name" => ""
    "parent" => 
    "id" => 
  ]
  9 => array:3 [▼
    "name" => ""
    "parent" => 
    "id" => 
  ]
  10 => array:3 [▼
    "name" => ""
    "parent" => 
    "id" => 
  ]

Another example deeper nesting 
{
   "name":"top",
   "id":xxx,
   "children":{
      "second":{
         "name":"second",
         "id":xxx,
         "children":{
            "Third":{
               "name":"third",
               "id":xxx,
               "children":{
                  "fourth":{
                     "name":"fourth",
                     "id":xxx
                  }
               }
            }
         }
      }
   }
}


$originalLength = count($data);
$obj = [];
while ($originalLength > 0) {
    foreach ($data as $item) {
        $name = $item['name'];
        $parent = $item['parent'];

        $a = isset($obj[$name]) ? $obj[$name] : array('name' => $name, 'id'=>$item['id']);

        if (($parent)) {

            $path = get_nested_path($parent, $obj, array(['']));
            try {
                insertItem($obj, $path, $a);
            } catch (Exception $e) {
                continue;
                //echo 'Caught exception: ', $e->getMessage(), "\n";
            }
        }

        $obj[$name] = isset($obj[$name]) ? $obj[$name] : $a;
        $originalLength--;
    }
}

echo json_encode($obj['A']);


function get_nested_path($parent, $array, $id_path)
{

    if (is_array($array) && count($array) > 0) {

        foreach ($array as $key => $value) {
            $temp_path = $id_path;

            array_push($temp_path, $key);

            if ($key == "id" && $value == $parent) {
                array_shift($temp_path);
                array_pop($temp_path);
                return $temp_path;
            }

            if (is_array($value) && count($value) > 0) {
                $res_path = get_nested_path(
                    $parent, $value, $temp_path);

                if ($res_path != null) {
                    return $res_path;
                }
            }
        }
    }
    return null;
}

function insertItem(&$array, $path, $toInsert)
{
    $target = &$array;
    foreach ($path as $key) {
        if (array_key_exists($key, $target))
            $target = &$target[$key];
        else throw new Exception('Undefined path: ["' . implode('","', $path) . '"]');
    }

    $target['children'] = isset($target['children']) ? $target['children'] : [];
    $target['children'][$toInsert['name']] = $toInsert;
    return $target;
}
Improve this question
10
  • Is it a specific requirement of the task you've been set that you don't use recursion? If not, what's the issue with it? Recursion is a valid solution to many kinds of problem. Commented Oct 5, 2022 at 9:40
  • I want to use this on a fairly large data set, around 10,000 items. My current solution is very resource heavy, as it is having to go back through the tree it is building to find the location to insert the child. Commented Oct 5, 2022 at 9:44
  • (looks like an Automattic coding challenge...) Commented Oct 5, 2022 at 9:47
  • Nope not a challenge. This is legit Commented Oct 5, 2022 at 9:58
  • very resource heavy...so it's slow, or using lots of memory, or both? What are the parameters of what you'd expect in order to make it work the way you want? Is there a max execution time and/or memory use and/or anything else that you'd find acceptable? Have you tried anything so far to optimise it? Commented Oct 5, 2022 at 10:06

1 Answer 1

Reset to default
4

Here's my take on what I believe is the desired output:

function buildTree(array $items): ?array {

    // Get a mapping of each item by ID, and pre-prepare the "children" property.
    $idMap = [];
    foreach ($items as $item) {
        $idMap[$item['id']] = $item;
        $idMap[$item['id']]['children'] = [];
    }

    // Store a reference to the treetop if we come across it.
    $treeTop = null;

    // Map items to their parents' children array.
    foreach ($idMap as $id => $item) {
        if ($item['parent'] && isset($idMap[intval($item['parent'])])) {
            $parent = &$idMap[intval($item['parent'])];
            $parent['children'][] = &$idMap[$id];
        } else if ($item['parent'] === null) {
            $treeTop = &$idMap[$id];
        }
    }

    return $treeTop;
}

This does two array cycles, one to map up the data by ID, then one to assign children to parents. Some key elements to note:

  • The build of $idMap in the first loop also effectively copies the items here so we won't be affecting the original input array (Unless it already contained references).
  • Within the second loop, there's usage of & to use references to other items, otherwise by default PHP would effectively create a copy upon assignment since these are arrays (And PHP copies arrays on assignment unlike Objects in PHP or arrays in some other languages such as JavaScript). This allows us to effectively share the same array "item" across the structure.
  • This does not protect against bad input. It's possible that invalid mapping or circular references within the input data could cause problems, although our function should always just be performing two loops, so should at least not get caught in an infinite/exhaustive loop.
Improve this answer
Sign up to request clarification or add additional context in comments.

14 Comments

While the above is brilliant, it does seem to have a flaw. It would appear objects in the array are being overwritten? I am making this assumption as there are items within the original data which are no longer present in the output result! Frustrating! But your answer does go to show that this can achieved without recursion, it is not yet perfect.
@JamesBaird Are you referring to actual objects? If so, they will behave differently. This solution is built to your provided example input, which has no objects within. Otherwise, do you have an example of input that fails the desired output? Based upon your example input, I see all those items in the output.
I will avoid using the word object as there is no object. This is an array of associative arrays. I have given two further examples pulled from the actual data source and anonymised. I can conform your solution produces a result where some of the entries are not present. I observed this on level four. I don’t understand why….
I just ran it again and again got a completely different outcome with entries missing. It is the strangest thing. I know my code is unnecessarily verbose and OTT but the result is always the same. Why is it a solution without recursion seems to fail??
and if you modify $treeTop with $treeTop[] it's going to work if you have more than one root category. Sorry about commenting but I found it great!
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.