Relational databases represent data as rows and columns inside a table; however, this representation is not suitable for hierarchical data. Certain models are available that allow you to store hierarchical data in these databases. One such method is the Adjacency List model. This article shows you how to manipulate adjacency list implementation of hierarchical (tree) data using PHP.
Hierarchical data consists of elements that have parent-child relationships. It can be visualized as a tree-like structure where each node can have one parent and many children. A node that does not have a parent is called root node while a node that does not have any children is called leaf node. Any connecting node is called branch node.
Adjacency list model is a naive solution used (unknowingly) by majority of programmers. In this implementation, each row stores a reference to its parent. This simplifies most database operations except for SELECTing a subtree (remember that the depth of the subtree is unknown).
Since a tree is a recursively defined data structure, it can be traversed naturally using recursion. The code demonstrated in this article uses (i) one query (ii) array to store all results (iii) index for faster iteration (iv) recursion. It does not use references or multiple queries.
The following data is used in the examples – a list of categories with unlimited depth:
Example Data
CREATE TABLE IF NOT EXISTS categories (
id INT(10) NOT NULL AUTO_INCREMENT,
parent_id INT(10) DEFAULT NULL,
name VARCHAR(50) DEFAULT NULL, PRIMARY KEY (id)
);
INSERT INTO categories (id, parent_id, name) VALUES
(1, NULL, 'Electronics'),
(2, 1, 'Cameras and Photography'),
(3, 1, 'Computers and Tablets'),
(4, 1, 'Cell Phones and Accessories'),
(5, 1, 'TV and Audio'),
(6, 2, 'Digital Cameras'),
(7, 2, 'Camcorders'),
(8, 2, 'Accessories'),
(9, 3, 'Laptops'),
(10, 3, 'Desktops'),
(11, 3, 'Netbooks'),
(12, 3, 'Tablets'),
(13, 4, 'Cell Phones'),
(14, 4, 'Smartphones'),
(15, 4, 'Accessories'),
(16, 5, 'Televisions'),
(17, 5, 'Home Audio'),
(18, 5, 'Speakers and Subwoofers'),
(19, 16, 'CRT'),
(20, 16, 'LCD'),
(21, 16, 'LED'),
(22, 16, 'Plasma'),
(23, 12, 'Android'),
(24, 12, 'iPad');
Basic Traversal
The following code prepares the hierarchical/tree data for traversal; then performs a traversal, listing all nodes, indented.
A single query retrieves all rows from the table and stores them in an associative array. The child-ids for each branch node are stored in another associative array, which is later used as a lookup table.
Finally there is a function that displays all children of the specified node. For each child, the function displays its name; then executes itself for the child. This function is kick-started by passing NULL – which results in displaying all nodes starting from the root.
<?php
/*
* PHP code to traverse hierarchical data (adjacency list model)
* https://salman-w.blogspot.com/2012/08/php-adjacency-list-hierarchy-tree-traversal.html
*/
$data = array();
$index = array();
$query = mysql_query("SELECT id, parent_id, name FROM categories ORDER BY name");
while ($row = mysql_fetch_assoc($query)) {
$id = $row["id"];
$parent_id = $row["parent_id"] === NULL ? "NULL" : $row["parent_id"];
$data[$id] = $row;
$index[$parent_id][] = $id;
}
/*
* Recursive top-down tree traversal example:
* Indent and print child nodes
*/
function display_child_nodes($parent_id, $level)
{
global $data, $index;
$parent_id = $parent_id === NULL ? "NULL" : $parent_id;
if (isset($index[$parent_id])) {
foreach ($index[$parent_id] as $id) {
echo str_repeat("-", $level) . $data[$id]["name"] . "\n";
display_child_nodes($id, $level + 1);
}
}
}
display_child_nodes(NULL, 0);
?>
The code produces the following output:
Electronics -Cameras and Photography --Accessories --Camcorders --Digital Cameras -Cell Phones and Accessories --Accessories --Cell Phones --Smartphones -Computers and Tablets --Desktops --Laptops --Netbooks --Tablets ---Android ---iPad -TV and Audio --Home Audio --Speakers and Subwoofers --Televisions ---CRT ---LCD ---LED ---Plasma
Bottom-up Traversal
The previous code example can be tweaked to perform a bottom-up (postorder, leaf to root) traversal. This traversal can be used to, for example, delete nodes of a subtree from bottom to top.
<?php
/*
* Recursive bottom-up tree traversal example:
* Delete child nodes
*/
function delete_child_nodes($parent_id)
{
global $data, $index;
$parent_id = $parent_id === NULL ? "NULL" : $parent_id;
if (isset($index[$parent_id])) {
foreach ($index[$parent_id] as $id) {
delete_child_nodes($id);
echo "DELETE FROM category WHERE id = " . $data[$id]["id"] . "\n";
}
}
}
delete_child_nodes(NULL);
?>
The code produces the following output, note the order in which delete queries are (supposed to) be executed:
DELETE FROM category WHERE id = 8 /* Accessories */ DELETE FROM category WHERE id = 7 /* Camcorders */ DELETE FROM category WHERE id = 6 /* Digital Cameras */ DELETE FROM category WHERE id = 2 /* Cameras and Photography */ DELETE FROM category WHERE id = 15 /* Accessories */ DELETE FROM category WHERE id = 13 /* Cell Phones */ DELETE FROM category WHERE id = 14 /* Smartphones */ DELETE FROM category WHERE id = 4 /* Cell Phones and Accessories */ DELETE FROM category WHERE id = 10 /* Desktops */ DELETE FROM category WHERE id = 9 /* Laptops */ DELETE FROM category WHERE id = 11 /* Netbooks */ DELETE FROM category WHERE id = 23 /* Android */ DELETE FROM category WHERE id = 24 /* iPad */ DELETE FROM category WHERE id = 12 /* Tablets */ DELETE FROM category WHERE id = 3 /* Computers and Tablets */ DELETE FROM category WHERE id = 17 /* Home Audio */ DELETE FROM category WHERE id = 18 /* Speakers and Subwoofers */ DELETE FROM category WHERE id = 19 /* CRT */ DELETE FROM category WHERE id = 20 /* LCD */ DELETE FROM category WHERE id = 21 /* LED */ DELETE FROM category WHERE id = 22 /* Plasma */ DELETE FROM category WHERE id = 16 /* Televisions */ DELETE FROM category WHERE id = 5 /* TV and Audio */ DELETE FROM category WHERE id = 1 /* Electronics */
Retrieving Nodes
The nodes can be retrieved after processing. You can make the recursive function modify its arguments like some PHP functions do (e.g. array_walk and array_push):
<?php
/*
* Retrieving nodes using variables passed as reference:
* Get ids of child nodes
*/
function get_child_nodes1($parent_id, &$children)
{
global $data, $index;
$parent_id = $parent_id === NULL ? "NULL" : $parent_id;
if (isset($index[$parent_id])) {
foreach ($index[$parent_id] as $id) {
$children[] = $id;
get_child_nodes1($id, $children);
}
}
}
$children = array();
get_child_nodes1(5, $children); /* TV and Audio */
echo implode("\n", $children);
?>
Output:
17 /* Home Audio */ 18 /* Speakers and Subwoofers */ 16 /* Televisions */ 19 /* CRT */ 20 /* LCD */ 21 /* LED */ 22 /* Plasma */
You can make the recursive function return a value like some other PHP functions do (e.g. array_reverse and array_unique):
<?php
/*
* Retrieving nodes using return statement:
* Get ids of child nodes
*/
function get_child_nodes2($parent_id)
{
$children = array();
global $data, $index;
$parent_id = $parent_id === NULL ? "NULL" : $parent_id;
if (isset($index[$parent_id])) {
foreach ($index[$parent_id] as $id) {
$children[] = $id;
$children = array_merge($children, get_child_nodes2($id));
}
}
return $children;
}
$children = get_child_nodes2(5); /* TV and Audio */
echo implode("\n", $children);
?>
Output:
17 /* Home Audio */ 18 /* Speakers and Subwoofers */ 16 /* Televisions */ 19 /* CRT */ 20 /* LCD */ 21 /* LED */ 22 /* Plasma */
Breadcrumbs
Since each node can have one parent, you can retrieve the breadcrumb (parents) of a node using a simple loop.
<?php
/*
* Display parent nodes
*/
function display_parent_nodes($id)
{
global $data;
$current = $data[$id];
$parent_id = $current["parent_id"] === NULL ? "NULL" : $current["parent_id"];
$parents = array();
while (isset($data[$parent_id])) {
$current = $data[$parent_id];
$parent_id = $current["parent_id"] === NULL ? "NULL" : $current["parent_id"];
$parents[] = $current["name"];
}
echo implode(" > ", array_reverse($parents));
}
display_parent_nodes(24); /* iPad */
?>
Electronics > Computers and Tablets > Tablets
