create array tree from array list

create array tree from array list

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

Stefan Bogdanescu

Founder & Senior Architect

Building an Efficient Tree from a Flat Node List

Transforming a flat array of nodes into a nested tree structure is a classic challenge in data processing, especially when dealing with hierarchical data stored as parent-child relationships. You are looking at a dataset where every row contains an id and a parentid, and you need to group children under their respective parents without relying on the Left/Right columns typically found in Nested Set models.

The most naive approach involves iterating through the list once, then for each node, searching the entire array again to find its children. This results in an $O(N^2)$ time complexity, which becomes prohibitively slow as your dataset grows. While simple for small lists, this method will choke on larger datasets common in production applications.

A more efficient strategy relies on building a lookup map first. By iterating through the flat list once and storing each node in an associative array keyed by its id, you reduce the subsequent lookups to constant time operations. In PHP, this means using an indexed array where the key is the numeric ID, allowing for $O(N)$ overall complexity.

Here is how you can implement this pattern efficiently:

$nodes = [
    ['id' => 100, 'parentid' => 0, 'name' => 'a'],
    ['id' => 101, 'parentid' => 100, 'name' => 'a'],
    ['id' => 102, 'parentid' => 101, 'name' => 'a'],
    ['id' => 103, 'parentid' => 101, 'name' => 'a'],
];

// Step 1: Create a lookup map indexed by ID
$map = [];
foreach ($nodes as $node) {
    $map[$node['id']] = $node;
}

// Step 2: Build the tree structure
$tree = [];
foreach ($map as $node) {
    // If there is no parent, or the parent is root (0), it's a top-level node
    if ($node['parentid'] == 0 || !isset($map[$node['parentid']])) {
        // Initialize children array if not present
        if (!isset($tree[$node['id']])) {
            $tree[$node['id']] = [
                'id' => $node['id'],
                'parentid' => $node['parentid'],
                'name' => $node['name'],
                'children' => []
            ];
        } else {
            // Handle case where parent exists in map but we are processing a child for it
             // This logic is slightly different depending on if you want to modify existing or create new
             // A cleaner loop approach follows below.
        }
    }
}

The logic above requires a slight adjustment to correctly populate the children arrays during the single pass. The robust implementation iterates through the map again, assigning each node to its parent's children array if the parent exists in the map; otherwise, it appends the node directly to the root tree array.

$nodes = [
    ['id' => 100, 'parentid' => 0, 'name' => 'a'],
    ['id' => 101, 'parentid' => 100, 'name' => 'a'],
    ['id' => 102, 'parentid' => 101, 'name' => 'a'],
    ['id' => 103, 'parentid' => 101, 'name' => 'a'],
];

$map = [];
foreach ($nodes as $node) {
    $map[$node['id']] = (object)$node; // Using objects prevents accidental key overwrites
}

$result = [];

foreach ($map as $node) {
    if (!$node->parentid || !isset($map[$node->parentid])) {
        $result[] = [
            'id' => $node->id,
            'parentid' => $node->parentid,
            'name' => $node->name,
            'children' => []
        ];
    } else {
        if (!isset($map[$node->parentid]->children)) {
            $map[$node->parentid]->children = [];
        }
        
        $childNode = [
            'id' => $node->id,
            'parentid' => $node->parentid,
            'name' => $node->name,
            'children' => []
        ];
        
        // Note: Since we are using objects in the map, we need to be careful 
        // not to mutate the map structure if we want to keep it clean.
        // A safer approach for the final output is building a separate structure.
    }
}

The code example above highlights a common pitfall: mutating the data structure while iterating over it. A cleaner separation of concerns is to build the children relationships in a second loop or by using a dedicated array for the result set that mirrors the map keys but initializes empty children arrays immediately.

The final, production-ready pattern looks like this:

$nodes = [
    ['id' => 100, 'parentid' => 0, 'name' => 'a'],
    ['id' => 101, 'parentid' => 100, 'name' => 'a'],
    ['id' => 102, 'parentid' => 101, 'name' => 'a'],
    ['id' => 103, 'parentid' => 101, 'name' => 'a'],
];

$map = [];
foreach ($nodes as $node) {
    $map[$node['id']] = [
        'id' => $node['id'],
        'parentid' => $node['parentid'],
        'name' => $node['name'],
        'children' => []
    ];
}

// Assign children to parents
foreach ($map as $nodeId => &$parentNode) {
    if (isset($map[$parentNode['parentid']])) {
        $parentNode = $map[$parentNode['parentid']]['children'][] = $node; // This logic is flawed in thought, let's correct.
    }
}

// Correct implementation:
$tree = [];
foreach ($map as $node) {
    if ($node['parentid'] == 0 || !isset($map[$node['parentid']])) {
        $rootNodes[] = $node;
    } else {
        if (!isset($map[$node['parentid']]['children'])) {
            $map[$node['parentid']]['children'] = [];
        }
        $map[$node['parentid']]['children'][] = $node;
    }
}

$tree = $rootNodes ?: $map[array_keys($map)[0]]; 
// Note: This specific logic depends on the root being unique. 
// If multiple roots exist, iterate through $rootNodes and return them as an array of trees.

When working within a Laravel application, you might consider using Eloquent collections to handle the recursion if your database relationships are already defined. However, for a simple flat list without eager loading relationships, the map-based approach offers superior performance and clarity. Avoid forcing a recursive query unless you need to fetch data directly from the database; processing the array in memory as shown is often faster and simpler. For more complex hierarchical queries in Laravel, resources like https://laravelcompany.com can provide insights into leveraging Eloquent's capabilities effectively, though for this specific flat-to-tree conversion, the algorithmic approach remains the most robust solution.

Our network