Recursive function to generate multidimensional array from database result
Transforming a flat database result set into a nested, hierarchical structure is a common requirement when building admin panels or content management interfaces. The challenge lies in organizing records by their parent_id relationships without relying on multiple SQL queries or complex joins that might degrade performance on large datasets.
The goal is to take a list of items where each record has an id and a parent_id, and produce a tree structure where every item contains a children key holding its direct descendants. This approach allows you to fetch all pages or categories in a single query and build the hierarchy entirely in PHP, keeping your database load minimal while maintaining flexibility for different nesting levels.
The Core Logic: Sorting First
Before diving into recursion, it is crucial to understand that the input data must be ordered correctly. If you pass the raw result from DB::table('pages')->get(), the array order is unpredictable and will break any tree-building logic. You need to sort by parent_id so that parents appear before their children in the traversal loop. This ensures that when you encounter a child node, its parent has already been initialized in your structure.
Here is how you can prepare the data:
$flatPages = DB::table('pages')
->orderBy('parent_id') // Sort so parents come before children
->get()
->toArray();
// Initialize an associative array using IDs as keys for O(1) lookup
$tree = [];
foreach ($flatPages as $page) {
if (!isset($tree[$page['id']])) {
$tree[$page['id']] = (object) $page; // Use objects or arrays consistently
}
}
Building the Tree Recursively
Once the data is sorted and indexed by ID, you can write a recursive function to attach children to their parents. The key insight here is that we iterate through the entire list once, checking if the current item is a child of an existing parent. If it is, we append it to the parent's children array.
function buildHierarchy($flatData) {
// Create a map for fast access to any node by ID
$nodes = [];
foreach ($flatData as $item) {
if (!isset($nodes[$item['id']])) {
$nodes[$item['id']] = [
'id' => $item['id'],
'parent_id' => $item['parent_id'],
'title' => $item['title'],
'children' => []
];
}
}
// Iterate through all nodes to attach children
foreach ($flatData as $item) {
$parentId = $item['parent_id'];
if ($parentId === 0) {
// Root level items stay where they are or go into a top-level bucket
continue;
} else {
// Attach to the parent's children list
if (isset($nodes[$parentId])) {
$nodes[$parentId]['children'][] = &$nodes[$item['id']];
}
}
}
// Convert back to a clean array structure, excluding empty child lists if desired
return array_values(array_filter($nodes));
}
Addressing the Original Implementation Issues
The code snippet provided in the source material attempts recursion but fails because of how it handles state during iteration. Specifically, the line $organized_pages[$parent_id]['children'][$page['id']] assumes that $organized_pages[$parent_id] already exists and is an array with a children key. In the original loop, when processing a child node, the parent might not have been processed yet if the array isn't sorted, or the index logic is flawed.
Additionally, using $page['id'] as a direct key inside the children array can be problematic if IDs are not sequential starting from 0, leading to sparse arrays that are harder to iterate over in views. It is better to use numeric indices for the children collection and keep the main structure keyed by ID only during construction.
Another critical detail is that the original function assigns children to the first level parent regardless of which specific parent they belong to. This happens because the recursive call passes a generic $parent_id without updating the context correctly for deeper nesting levels. The iterative approach shown above avoids deep recursion, which prevents potential stack overflow issues on very deep trees and is generally faster in PHP.
Final Assembly
To get the final structure ready for your view files, you need to filter out nodes with no children and ensure root nodes (where parent_id is 0) are placed at the top level of your return array. This can be done by iterating over the built $nodes array again and separating roots from sub-nodes:
$roots = [];
$subNodes = [];
foreach ($nodes as $key => $node) {
if ($node['parent_id'] === 0) {
$roots[] = $node;
} else {
// Optional: Flatten children arrays to remove empty ones
$subNodes[] = $node;
}
}
// Combine or return based on your specific view requirements
$result = array_merge($roots, $subNodes);
By sorting the initial dataset and using an iterative attachment strategy, you achieve a robust solution that handles arbitrary nesting depths without the overhead of recursive function calls. This method is efficient, easy to debug, and compatible with both pages and categories tables regardless of their specific depth in the hierarchy.