How to generate an array of binary structure using Nested Set?

Question

PHP

I use Nested Set to build user structures and came across the following question:
For example, we have the following code to generate a list:

foreach ($struct as $n => $user)
    {
        if ($user['level'] == $level) {
            echo Html::endTag('li') . "\n";
        } elseif ($user['level'] > $level) {
            echo Html::beginTag('ul') . "\n";
        } else {
            echo Html::endTag('li') . "\n";
    
            for ($i = $level - $user['level']; $i; $i--) {
                echo Html::endTag('ul') . "\n";
                echo Html::endTag('li') . "\n";
            }
        }
    
        echo Html::beginTag('li');
        echo $user['user_id'];
        $level = $user['level'];
    }
    
    for ($i = $level; $i; $i--) {
        echo Html::endTag('li') . "\n";
        echo Html::endTag('ul') . "\n";
    }

At the exit:

500
    501
    533
        516
504
    505
        506

$struct array:

Array
(
    [0] => Array
        (
            [user_id] => 500
            [previous_id] => 234
            [side] => R
            [lft] => 2
            [rgt] => 9
            [level] => 2
        )

    [1] => Array
        (
            [user_id] => 501
            [previous_id] => 500
            [side] => R
            [lft] => 3
            [rgt] => 4
            [level] => 3
        )

    [2] => Array
        (
            [user_id] => 533
            [previous_id] => 500
            [side] => L
            [lft] => 5
            [rgt] => 8
            [level] => 3
        )

    [3] => Array
        (
            [user_id] => 516
            [previous_id] => 533
            [side] => L
            [lft] => 6
            [rgt] => 7
            [level] => 4
        )

    [4] => Array
        (
            [user_id] => 504
            [previous_id] => 234
            [side] => L
            [lft] => 10
            [rgt] => 15
            [level] => 2
        )

    [5] => Array
        (
            [user_id] => 505
            [previous_id] => 504
            [side] => L
            [lft] => 11
            [rgt] => 14
            [level] => 3
        )

    [6] => Array
        (
            [user_id] => 506
            [previous_id] => 505
            [side] => L
            [lft] => 12
            [rgt] => 13
            [level] => 4
        )

)

I need to render a binary structure.

The problem is that I can't generate a suitable array.
Please tell me how this array is, you can generate something like this:

Array
(
    [0] => Array
        (
            [0] => Array
                (
                    [user_id] => 500
                    [previous_id] => 234
                    [side] => L
                )

            [1] => Array
                (
                    [user_id] => 504
                    [previous_id] => 234
                    [side] => R
                )

        )

    [1] => Array
        (
            [0] => Array
                (
                    [user_id] => 501
                    [previous_id] => 500
                    [side] => L
                )

            [1] => Array
                (
                    [user_id] => 533
                    [previous_id] => 500
                    [side] => R
                )

            [2] => Array
                (
                    [user_id] => 505
                    [previous_id] => 504
                    [side] => L
                )

            [3] => Array
                (
                )

        )

    [3] => Array
        (
            [0] => Array
                (
                )

            [1] => Array
                (
                )

            [2] => Array
                (
                    [user_id] => 516
                    [previous_id] => 533
                    [side] => L
                )

            [3] => Array
                (
                )

            [4] => Array
                (
                    [user_id] => 506
                    [previous_id] => 505
                    [side] => L
                )

            [5] => Array
                (
                )

            [6] => Array
                (
                )

            [7] => Array
                (
                )

        )

)

Answer 1

You will have a structure like the one below, where subitems is an array of elements of the same structure. In data store the payload for the node (in your case user_id, L, R):

array(
'id' => ...,
'data' => array(...),
'subitems' => array(...)
)

Get an index array of links $node_index = array(); and an array of results $result = array();
Sort the original array in ascending level, and then do something like:

foreach($node in $source_array) {
   if(!($parent_node = $node_index[$node['previous_id']])) {
       $result[$node['previous_id']] = array(
           'id' => $node['previous_id'],
           'data' => array(...),
           'subitems' => array()
       );
       $node_index = &$result[$node['previous_id']];
       $parent_node = $node_index[$node['previous_id']];
   }
   $parent_node['subitems'][$node['id']] = $node;
   $node_index[$node['id']] = &$parent_node['subitems'][$node['id']];
}

I can not say that the code is 100% working, I wrote it from memory. Its essence is that $node_index is a hash of the node id => a link to it. Without this array, recursion would have to be tricky in order to shove the elements along the hierarchy.
As a result, you will get a hierarchical array, bypassing which you can recursively visualize it.
And if it’s completely good, then it’s better to use some kind of ready-made tree. This is so, dirty hack, nothing more.