How to use a recursive function to generate multidimensional array from database result?

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Using a Recursive Function to Generate a Multidimensional Array from Database Results in PHP

Transforming flat database results into a hierarchical (multidimensional) array is a common requirement, especially when dealing with data that inherently possesses a parent-child relationship, such as organizational structures, category trees, or file systems. PHP, with its robust array handling capabilities, provides an efficient way to achieve this using recursive functions.

Scenario Overview

Assume you have a database table named categories structured as follows:

id	parent_id	name
1	0	Electronics
2	1	Computers
3	1	Mobile Phones
4	2	Laptops
5	2	Desktops
6	3	Smartphones
7	3	Feature Phones

Here, parent_id refers to the id of the parent category. A parent_id of 0 signifies a root category.

Objective

Convert the flat list of categories into a nested multidimensional array representing the hierarchical structure:

[
    [
        'id' => 1,
        'name' => 'Electronics',
        'children' => [
            [
                'id' => 2,
                'name' => 'Computers',
                'children' => [
                    ['id' => 4, 'name' => 'Laptops', 'children' => []],
                    ['id' => 5, 'name' => 'Desktops', 'children' => []],
                ],
            ],
            [
                'id' => 3,
                'name' => 'Mobile Phones',
                'children' => [
                    ['id' => 6, 'name' => 'Smartphones', 'children' => []],
                    ['id' => 7, 'name' => 'Feature Phones', 'children' => []],
                ],
            ],
        ],
    ],
]

Step-by-Step Implementation

Fetch Data from the Database

First, retrieve the categories from the database. Ensure that the results are sorted or indexed in a way that facilitates easy lookup.

<?php
// Database connection parameters
$host = 'localhost';
$db   = 'your_database';
$user = 'your_username';
$pass = 'your_password';
$charset = 'utf8mb4';

$dsn = "mysql:host=$host;dbname=$db;charset=$charset";
$options = [
    PDO::ATTR_ERRMODE            => PDO::ERRMODE_EXCEPTION,
    PDO::ATTR_DEFAULT_FETCH_MODE => PDO::FETCH_ASSOC,
    PDO::ATTR_EMULATE_PREPARES   => false,
];

try {
    $pdo = new PDO($dsn, $user, $pass, $options);
} catch (\PDOException $e) {
    throw new \PDOException($e->getMessage(), (int)$e->getCode());
}

// Fetch all categories
$stmt = $pdo->query('SELECT id, parent_id, name FROM categories');
$categories = $stmt->fetchAll();
?>

Organize Data for Efficient Lookup

To optimize the recursive function, it's beneficial to index the categories by their parent_id. This approach minimizes the number of iterations needed to find child categories.

<?php
// Index categories by parent_id
$indexedCategories = [];
foreach ($categories as $category) {
    $parentId = $category['parent_id'];
    if (!isset($indexedCategories[$parentId])) {
        $indexedCategories[$parentId] = [];
    }
    $indexedCategories[$parentId][] = $category;
}
?>

Define the Recursive Function

The recursive function will traverse the indexed categories, building the nested structure by attaching child categories to their respective parents.

<?php
/**
 * Recursively builds a hierarchical tree from indexed categories.
 *
 * @param int $parentId The ID of the parent category.
 * @param array $indexedCategories The array of categories indexed by parent_id.
 * @return array The hierarchical tree structure.
 */
function buildTree($parentId, $indexedCategories) {
    $tree = [];

    if (isset($indexedCategories[$parentId])) {
        foreach ($indexedCategories[$parentId] as $category) {
            $children = buildTree($category['id'], $indexedCategories);
            if ($children) {
                $category['children'] = $children;
            } else {
                $category['children'] = [];
            }
            $tree[] = $category;
        }
    }

    return $tree;
}

// Build the tree starting from parent_id = 0 (root categories)
$hierarchicalCategories = buildTree(0, $indexedCategories);
?>

Result

The $hierarchicalCategories variable now holds the multidimensional array representing the hierarchical structure of categories.

<?php
echo '<pre>';
print_r($hierarchicalCategories);
echo '</pre>';
?>

Output:

Explanation of the Recursive Function

Base Case: If a category has no children (i.e., there are no entries in $indexedCategories with parent_id equal to the current category's id), the function returns an empty array for children.
Recursive Case: For each category, the function calls itself to find and attach any child categories, building the nested structure.

Optimizations and Best Practices

Indexing for Performance:

By indexing categories by parent_id, the function avoids repeatedly scanning the entire list of categories to find children, significantly improving performance, especially with large datasets.
Handling Multiple Roots:

The function starts building the tree from parent_id = 0, allowing for multiple root categories if your data supports them.
Avoiding Excessive Memory Usage:

For extremely large category trees, consider implementing iterative approaches or using generators to manage memory consumption efficiently.
Validation and Error Handling:

Ensure that the parent_id values correctly reference existing id values to prevent orphaned categories. Implement checks to handle orphans as per your application's requirements.

Using Classes for Enhanced Structure:

While arrays are sufficient for simple hierarchies, using classes to represent categories can provide additional functionality and enforce structure.

<?php
class Category {
    public $id;
    public $parent_id;
    public $name;
    public $children = [];

    public function __construct($id, $parent_id, $name) {
        $this->id = $id;
        $this->parent_id = $parent_id;
        $this->name = $name;
    }
}

function buildCategoryTree($parentId, $indexedCategories) {
    $tree = [];

    if (isset($indexedCategories[$parentId])) {
        foreach ($indexedCategories[$parentId] as $categoryData) {
            $category = new Category($categoryData['id'], $categoryData['parent_id'], $categoryData['name']);
            $category->children = buildCategoryTree($category->id, $indexedCategories);
            $tree[] = $category;
        }
    }

    return $tree;
}

$hierarchicalCategories = buildCategoryTree(0, $indexedCategories);

// Example of accessing data
foreach ($hierarchicalCategories as $category) {
    echo $category->name . "\n";
    foreach ($category->children as $child) {
        echo "  - " . $child->name . "\n";
        foreach ($child->children as $grandchild) {
            echo "    * " . $grandchild->name . "\n";
        }
    }
}
?>

Output:

Electronics
  - Computers
    * Laptops
    * Desktops
  - Mobile Phones
    * Smartphones
    * Feature Phones

Preventing Infinite Recursion:

Ensure that your data does not contain cyclic relationships (e.g., a category being its own ancestor), which can cause infinite recursion and crash your application. Implement checks or constraints in your database to prevent such scenarios.

Alternative Approach: Iterative Method

While recursion is intuitive for hierarchical data, an iterative approach can be more efficient and less prone to stack overflow errors with deeply nested structures.

<?php
function buildTreeIterative($indexedCategories, $rootId = 0) {
    $tree = [];
    $stack = [];

    // Initialize stack with root categories
    if (isset($indexedCategories[$rootId])) {
        foreach ($indexedCategories[$rootId] as $category) {
            $tree[] = $category;
            $stack[] = &$tree[count($tree) - 1];
        }
    }

    while (!empty($stack)) {
        $current = array_pop($stack);
        $currentId = $current['id'];

        if (isset($indexedCategories[$currentId])) {
            foreach ($indexedCategories[$currentId] as $child) {
                $current['children'][] = $child;
                $stack[] = &$current['children'][count($current['children']) - 1];
            }
        }
    }

    return $tree;
}

$hierarchicalCategories = buildTreeIterative($indexedCategories);
?>

Note: Iterative methods can be more complex to implement but offer better control over the recursion depth and stack usage.

Conclusion

Generating a multidimensional array from a flat database result with parent-child relationships in PHP is efficiently achievable using recursive functions. By indexing the data and carefully constructing the recursive logic, you can build complex hierarchical structures that are both manageable and performant. Whether you choose a recursive or iterative approach depends on your specific use case, data size, and performance considerations.

Further Resources

Happy Coding!