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: stackoverflow.com/questions/22784060/retrieve-hierarchical-data/… — Maximilian Riegler
– Maximilian Riegler, Commented Aug 13, 2014 at 7: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 which allows to retrieve branches with one query. — Yoshi
– Yoshi, Commented Aug 13, 2014 at 7:45
Just give it a maximum recursion depth and there'll be no problems at all. — Maximilian Riegler
– Maximilian Riegler, Commented Aug 13, 2014 at 7:47
Found a good solution here: stackoverflow.com/questions/8587341/… — Ron
– Ron, Commented Jun 1, 2015 at 13:36
Related page: Transform simple array in hierarchy array Implementation of one of the answers: 3v4l.org/UGXFf — mickmackusa
– mickmackusa ♦, Commented Feb 6, 2023 at 21:18

Yoshi · Accepted Answer · 2014-08-13 08:16:18Z

2

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

answered Aug 13, 2014 at 8:16

Yoshi

54.8k14 gold badges93 silver badges108 bronze badges

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

2 Comments

Yoshi Over a year ago

@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.

Jean Y.C. Yang Over a year ago

Thanks! I really don't know how data structure works... I have to read more books about nodes and trees.

georg · Accepted Answer · 2014-08-13 08:16:11Z

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, 2014 at 8:16

georg

216k57 gold badges324 silver badges401 bronze badges

4 Comments

Yoshi Over a year ago

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.

georg Over a year ago

@Yoshi: I'm not sure if it's really a problem. Even with thousands of nodes the loop will be lighting fast.

Yoshi Over a year ago

I'm a bit baffled. Saying that whether a loop runs n² or n times is irrelevant, seems a bit extreme to me...

georg Over a year ago

@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.

Botea Florin · Accepted Answer · 2023-02-06 16:56:45Z

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);```

Collectives™ on Stack Overflow

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

3 Answers 3

2 Comments

4 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related