Deprecated Behaviour

The inane, sometimes insane, ramblings from the mind of Brenton Alker.

Converting a Flat Array With Parent ID's to a Nested Tree

Storing hierarchical data in a tabular data structure such as a database is not uncommon in many applications (eg. threaded comments on a blog entry, or a navigation menu structure). The “Adjacency List” method; probably the most common, involves storing a reference to the parent in each of the children.

Here is a snippet for converting the rows stored using the adjacency list method into a hierarchical array in PHP. My goal was to do this in 1 pass, without recursion. I ended up using 2 passes, I think 1 pass is achievable if you can guarantee the parent will always be returned before all of its children. But since I couldn’t, the first pass is to change the id of the row to be the key of the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

<?php
function convertToTree(array $flat, $idField = 'id',
                        $parentIdField = 'parentId',
                        $childNodesField = 'childNodes') {
    $indexed = array();
    // first pass - get the array indexed by the primary id  
    foreach ($flat as $row) {
        $indexed[$row[$idField]] = $row;
        $indexed[$row[$idField]][$childNodesField] = array();
    }

    //second pass  
    $root = null;
    foreach ($indexed as $id => $row) {
        $indexed[$row[$parentIdField]][$childNodesField][$id] =& $indexed[$id];
        if (!$row[$parentIdField]) {
            $root = $id;
        }
    }

    return array($root => $indexed[$root]);
}

// Usage:
$rows = array(
    array(
        'id' => 1,
        'parentId' => null,
        'name' => 'Menu',
    ),
    array(
        'id' => 2,
        'parentId' => 1,
        'name' => 'Item 1-1',
    ),
    array(
        'id' => 3,
        'parentId' => 1,
        'name' => 'Item 2-1',
    ),
    array(
        'id' => 4,
        'parentId' => 1,
        'name' => 'Item 1-2',
    ),
);

convertToTree($rows);

// Produces:
array (
    1 => array(
        'id' => 1,
        'parentId' => NULL,
        'name' => 'Menu',
        'childNodes' => array(
            2 => array(
                'id' => 2,
                'parentId' => 1,
                'name' => 'Item 1-1',
                'childNodes' => array (
                    4 => array (
                        'id' => 4,
                        'parentId' => 2,
                        'name' => 'Item 1-2',
                        'childNodes' => array (
                        ),
                    ),
                ),
            ),
            3 =>  array (
                'id' => 3,
                'parentId' => 1,
                'name' => 'Item 2-1',
                'childNodes' => array (
                ),
            ),
        ),
    ),
)