Build a tree from a flat array in PHP

Build a tree from a flat array in PHP

  1. Blog
  2. 15 November 2026
  3. 3 min read

Stefan Bogdanescu

Founder & Senior Architect

Build a tree from a flat array in PHP

Transforming a flat list of records into a hierarchical structure is a common requirement when dealing with nested data like file systems, category lists, or permission trees. The core challenge lies in efficiently matching parent-child relationships without mutating the original dataset or creating multiple full copies of nodes during the traversal.

When starting with an array where each element has an id and a parent_id, the naive approach often involves iterating through the list repeatedly. For every node found with a specific parent, you iterate again to find its children. This results in $O(n^2)$ time complexity, which degrades rapidly as the dataset grows. A more efficient strategy utilizes associative arrays (hash maps) to achieve $O(n)$ performance by establishing a direct lookup for every parent ID before processing the hierarchy.

The solution relies on two distinct phases: index creation and recursive assembly.

Phase 1: Index Creation

First, you must map every id to its corresponding node data. This allows you to instantly retrieve a child node when you encounter it in a parent's context. In PHP, this is done by iterating once over the flat array and populating a new associative array where the key is the node's id.

$nodes = [];
foreach ($flatArray as $item) {
    // Ensure we use the correct ID field for the key
    // Based on source material, keys might be strings like '_320_', 
    // but the 'id' value inside is also a string.
    $key = (string)$item['id']; 
    $nodes[$key] = $item;
}

In the provided source example, the array keys are strings (e.g., '_319_'), and the id values are also strings. It is crucial to normalize these values. If the id inside the data is '0', use that for the lookup key. If it represents a root node with no parent, the parent_id field will be 0.

Phase 2: Recursive Assembly

Once the lookup table is ready, you can build the tree recursively. You iterate through the indexed nodes, checking each one's parent_id. If a node matches the current depth's expected parent ID (starting at 0 for roots), it becomes part of that branch.

Crucially, instead of copying data into a new array in a way that leaves duplicates behind, we modify the specific node instance retrieved from our index and attach its children to it. This ensures the final structure mirrors the desired output where each node appears exactly once under its parent.

function buildTree(array $nodes, $parentId = 0) {
    $branch = [];

    foreach ($nodes as $nodeId => $element) {
        if ((string)$element['parent_id'] === (string)$parentId) {
            // Recursively find children for this specific node ID
            $children = buildTree($nodes, $element['id']);
            
            if (!empty($children)) {
                $element['children'] = $children;
            }

            $branch[] = $element;
        }
    }

    return $branch;
}

Handling the Root and Edge Cases

A common pitfall in this pattern is how the function handles nodes with no parent. In your specific example, root items have parent_id set to 0. The initial call to buildTree defaults to $parentId = 0, which correctly captures all roots. However, you must ensure that a node's own id (e.g., '_320_') is treated differently from its parent_id ('0').

If your data contains cycles or orphaned nodes pointing to non-existent parents, this logic will fail silently or throw errors depending on how the recursive call handles missing keys. Always validate that the recursive lookup exists before attempting to attach children.

Performance Considerations

This approach scales linearly relative to the number of elements. By separating the indexing step from the traversal, you avoid the nested loops inherent in naive implementations. If you are processing large datasets within a Laravel application, consider passing the indexed array by reference or utilizing Laravel collections if type safety and chainability add value to your specific use case. The logic remains fundamentally the same, but wrapping it in a Service class keeps your controllers clean.

For production environments where data integrity is paramount, always normalize numeric IDs to strings before using them as associative array keys. This prevents issues where 0 (integer) and '0' (string) are treated as distinct keys, which often leads to missing children during the tree construction phase.

Our network