Create tree structure in PHP with given depth, root and parent amount of children

Question

I have one user which I will consider the root element of my tree structure. Afterwards I have an array of users coming from my database which I consider all the children elements of the tree.

The building of the tree needs to contain the following variables that determine the width and depth of the tree:

Variable: MATCHES_TREE_MAX_DEPTH (eg: 3)
Variable: MATCHES_TREE_ROOT_MAX_CHILDREN_AMOUNT (eg: 2)
Variable: MATCHES_TREE_PARENT_MAX_CHILDREN_AMOUNT (eg: 1)

This means that I want to create a tree structure that is depth 3 (this includes the root element, so I want 2 levels deeper). The root element has 2 children, while any children of children will have have maximum 1 child element.

The order the items are in my users array is the order I want to insert them in the tree (I want to insert them breadth first rather than depth first).

I have found the following generic function on SO: PHP - How to build tree structure list? But I don't seem to be able to adapt it to my use case, since I do not have a parent-child relationship coming from my database.

This SO answer returns me an array that is looking similar, but I'm having issues reforming it to my use case: PHP generate a tree by specified depth and rules

Example data looks like this:

Root user:

object(stdClass)[56]
  public 'user_id' => string '1' (length=1)
  public 'first_name' => string 'Dennis' (length=6)

Other users (children):

array (size=3)
  0 => 
    object(stdClass)[57]
      public 'user_id' => string '2' (length=2)
      public 'first_name' => string 'Tom' (length=3)
      public 'street' => string 'Teststreet' (length=10)
  1 => 
    object(stdClass)[58]
      public 'user_id' => string '3' (length=2)
      public 'first_name' => string 'Mary' (length=1)
      public 'street' => string 'Maryland avenue' (length=15)
  2 => 
    object(stdClass)[59]
      public 'user_id' => string '4' (length=2)
      public 'first_name' => string 'Jeff' (length=4)
      public 'street' => string 'Teststreet' (length=10)

An example of the tree I want to achieve with the examples filled (taking into account the variables of 3 max depth, 2 children of root and 1 max children of any other element than the root):

Array
(
    [userid] => 1
    [name] => "Dennis"
    [matches] => Array
        (
            [0] => Array
                (
                    [userid] => 2
                    [name] => "Tom"
                    [street] => "Teststreet"
                    [matches] => Array
                        (
                            [0] => Array
                                (
                                    [userid] => 4
                                    [name] => "Jeff"
                                    [street] => "Teststreet"
                                    [matches] = Array()
                                )
                        )
                )

            [1] => Array
                (
                    [userid] => 3
                    [name] => "Mary"
                    [street] => "Maryland avenue"
                    [matches] => Array
                        (
                        )
                )
        )
)

How do I create this tree structure given the 3 variables that determine the depth and children?

Answer 1

EDIT: I see that the original question is looking for a solution that works with the 3 constants. I've added to the code so it's possible to define constants and loop based on them, but I am not sure I understand how one is supposed to use all three variables. In particular, MATCHES_TREE_MAX_DEPTH seems out of place given your descriptions. You indicated only two levels of children and instructed that we should skip any additional items in your list. If you want code that defines still more levels of children, you'll need to be clearer about how you want your structure to grow.

Given the very narrow limits described to this problem in the additional comments, it seems like a waste of effort to agonize over loops to handle this problem. This tree can't ever have more than five elements so an iterative solution like this should work:

// function to convert from list objects to the array we want as output
function new_obj($obj) {
    $ret = array(
        "userid" => $obj->user_id,
        "name" => $obj->first_name
    );
    if (isset($obj->street)) {
        $ret["street"] = $obj->street;
    }
    $ret["matches"] = [];
    return $ret;
}


// INPUT DATA
$root = (object)["user_id" => "1", "first_name" => "Dennis"];
$children = [
    (object)[
        "user_id" => "2",
        "first_name" => "Tom",
        "street" => "Teststreet"
    ],
    (object)[
        "user_id" => "3",
        "first_name" => "Mary",
        "street" => "Maryland avenue"
    ],
    (object)[
        "user_id" => "4",
        "first_name" => "Jeff",
        "street" => "Teststreet"
    ],
    (object)[
        "user_id" => "5",
        "first_name" => "Arthur",
        "street" => "Teststreet"
    ]

];

$result1 = new_obj($root);

// an iterative solution, only works for one trivial set of values for the constants defined
// but also does provide some insight into a more general solution
if (isset($children[0])) {
    $result1["matches"][0] = new_obj($children[0]);
}
if (isset($children[1])) {
    $result1["matches"][1] = new_obj($children[1]);
}
if (isset($children[2])) {
    $result1["matches"][0]["matches"][0] = new_obj($children[2]);
}
if (isset($children[3])) {
    $result1["matches"][1]["matches"][0] = new_obj($children[3]);
}


print_r($result1);

If you want to define constants/vars to specify child limits and then use loops, try this with the same $root and $children vars defined above.

// solution must use these constants:
define("MATCHES_TREE_MAX_DEPTH", 3);
define("MATCHES_TREE_ROOT_MAX_CHILDREN_AMOUNT", 2);
define("MATCHES_TREE_PARENT_MAX_CHILDREN_AMOUNT", 1);

$result2 = new_obj($root);

$i = 0;
while ($child = array_shift($children)) {
    $result2["matches"][$i] = new_obj($child);
    $i++;
    if ($i >= MATCHES_TREE_ROOT_MAX_CHILDREN_AMOUNT) break;
}

$i = 0;
while ($grandchild = array_shift($children)) {
    $child = $result2["matches"][$i];
    if (count($child["matches"]) >= MATCHES_TREE_PARENT_MAX_CHILDREN_AMOUNT) {
        // if we reach a child that has its max number of grandchildren, it's time to quit
        break;
    }
    // otherwise, assign this child as a grandchild
    $result2["matches"][$i]["matches"] = new_obj($grandchild);

    // increment the counter and check if we cycle back to the first child of root
    $i++;
    if ($i >= count($result2["matches"])) {
        $i = 0;
    }
}
print_r($result2);