How to build a "child-parent" tree/nested array from database?

Question

TABLE `people`
+----+------------+-------+
| sn | name       | upper |
+----+------------+-------+
|  1 | Clement    |     0 |
|  2 | Jean       |     1 |
|  3 | Annie      |     1 |
|  4 | Yuan       |     2 |
|  5 | Mei        |     2 |
|  6 | Blue       |     3 |
|  7 | Yang       |     5 |
|  8 | Lorinda    |     0 |
+----+------------+-------+

The structure is like:

Clement
    Jean
        Yuan
        Mei
            Yang
    Annie   
        Blue
Lorinda

The column upper states the upper person of himself/herself.

The problem is: How can I get a nested/multi-dimensional array from MySQL? I thought I could use loops to fetch, but I failed to automated fetch all the lowers. The array could be like this:

Array
(
    [1]=>Array
    (
        [self]=>Clement
        [2]=>Array
        (
            [self]=>Jean
            [4]=>Array
            (
                [self]=>Yuan
            )
            [5]=>Array
            (
                [self]=>Mei
                [7]=>Array
                (
                    [self]=>Yang
                )
            )
        )
        [3]=>Array
        (
            [self]=>Annie
            [6]=>Array
            (
                [self]=>Blue
            )
        )
    )
    [8]=>Array
    (
        [self]=>Lorinda
    )
)

Since we don't know how many 'upper' persons does one have, the solution should be an automated function that build a complete array, not just for three or four dimension. In other word, the function should deep into all the lower person from a top person.

I answered a similar question a while ago: http://stackoverflow.com/questions/22784060/retrieve-hierarchical-data/22784613#22784613 — Maximilian Riegler, Aug 13 '14 at 07:42
Please, never every build recursive sql-queries. You're guaranteed to run into problems. There are ways to build the tree with a simple foreach loop if you have all data in a flat array. Though you'll have to retrieve all data from the database. If that's not possible have a look at the [nested set model](https://en.wikipedia.org/wiki/Nested_set_model) which allows to retrieve branches with one query. — Yoshi, Aug 13 '14 at 07:45
Just give it a maximum recursion depth and there'll be no problems at all. — Maximilian Riegler, Aug 13 '14 at 07:47
Found a good solution here: http://stackoverflow.com/questions/8587341/recursive-function-to-generate-multidimensional-array-from-database-result — Ron, Jun 01 '15 at 13:36
Related page: [Transform simple array in hierarchy array](https://stackoverflow.com/q/33463194/2943403) Implementation of one of the answers: https://3v4l.org/UGXFf — mickmackusa, Feb 06 '23 at 21:18

score 2 · Accepted Answer · answered Aug 13 '14 at 08:16

Given your input as:

$input = array(
  array('sn' => 1, 'name' => 'Clement', 'upper' => 0),
  array('sn' => 2, 'name' => 'Jean',    'upper' => 1),
  array('sn' => 3, 'name' => 'Annie',   'upper' => 1),
  array('sn' => 4, 'name' => 'Yuan',    'upper' => 2),
  array('sn' => 5, 'name' => 'Mei',     'upper' => 2),
  array('sn' => 6, 'name' => 'Blue',    'upper' => 3),
  array('sn' => 7, 'name' => 'Yang',    'upper' => 5),
  array('sn' => 8, 'name' => 'Lorinda', 'upper' => 0),
);

using references you can build a tree with the following loop:

$map = array();

foreach ($input as $node) {
  // init self
  if (!array_key_exists($node['sn'], $map)) {
    $map[$node['sn']] = array('self' => $node['name']);
  }
  else {
    $map[$node['sn']]['self'] = $node['name'];
  }

  // init parent
  if (!array_key_exists($node['upper'], $map)) {
    $map[$node['upper']] = array();
  }

  // add to parent
  $map[$node['upper']][$node['sn']] = & $map[$node['sn']];
}

print_r($map[0]);

demo: http://3v4l.org/vuVPu

@JeanYang The distinction ensures that the data does not have to be sorted in any way. So a child node could come before it's parent and the function would still work. — Yoshi, Aug 13 '14 at 09:07
Thanks! I really don't know how data structure works... I have to read more books about nodes and trees. — Jean Y.C. Yang, Aug 13 '14 at 09:19

score 0 · Answer 2 · answered Aug 13 '14 at 08:16

0

Assuming the data is like this

$data = array(
    array(1, 'Clement', 0),
    array(2, 'Jean   ', 1),
    array(3, 'Annie  ', 1),
    array(4, 'Yuan   ', 2),
    array(5, 'Mei    ', 2),
    array(6, 'Blue   ', 3),
    array(7, 'Yang   ', 5),
    array(8, 'Lorinda', 0),
);

this recursive function might work:

function tree($data, $node) {
    foreach($data as $e)
        if($e[2] == $node[0])
            $node['children'] []= tree($data, $e);
    return $node;
}

Use it like this:

$tree = tree($data, array(0));
print_r($tree);

answered Aug 13 '14 at 08:16

georg

211,518
52
313
390

The problem with this function is that for each node the whole array has to be traversed, which can get quite expensive if there're more entries. – Yoshi Aug 13 '14 at 08:32
1

@Yoshi: I'm not sure if it's really a problem. Even with thousands of nodes the loop will be lighting fast. – georg Aug 13 '14 at 08:34
I'm a bit baffled. Saying that whether a loop runs `n²` or `n` times is irrelevant, seems a bit extreme to me... – Yoshi Aug 14 '14 at 10:17
@Yoshi: why? If the whole thing takes, say, 20 sec, and this specific function 0.002 sec, would it really be worth optimizing? We don't know anything about the OP's project, but I guess one single DB query will take more resources than this function, no matter how efficient it is. – georg Aug 14 '14 at 10:43

score 0 · Answer 3 · answered Feb 06 '23 at 16:56

using a reference map

$input = array(
  array('sn' => 1, 'name' => 'Clement', 'upper' => 0),
  array('sn' => 2, 'name' => 'Jean',    'upper' => 1),
  array('sn' => 3, 'name' => 'Annie',   'upper' => 1),
  array('sn' => 4, 'name' => 'Yuan',    'upper' => 2),
  array('sn' => 5, 'name' => 'Mei',     'upper' => 2),
  array('sn' => 6, 'name' => 'Blue',    'upper' => 3),
  array('sn' => 7, 'name' => 'Yang',    'upper' => 5),
  array('sn' => 8, 'name' => 'Lorinda', 'upper' => 0),
);

$map = []; // map a reference by id for each item
foreach ($input as &$inp) {
  $map[$inp['sn']] = &$inp;
}

foreach ($map as &$_inp) { // assign each item to its parent, with help of the map
  if ($_inp['upper']) {
    $map[$_inp['upper']]['children'] = &$map[$_inp['upper']]['children'] ?? [];
    $map[$_inp['upper']]['children'][] = &$_inp;
  }
}
$result = array_filter($map, fn($item) => !$item['upper']);

print_r($result);```

How to build a "child-parent" tree/nested array from database?

3 Answers3

Linked