Convert a series of parent-child relationships into a hierarchical tree?

Convert a series of parent-child relationships into a hierarchical tree?

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

Stefan Bogdanescu

Founder & Senior Architect

Building Hierarchical Trees from Flat Parent-Child Data

Transforming a flat list of parent-child relationships into a nested tree structure is a classic algorithmic challenge. You have an array of pairs where each child maps to its parent, and your goal is to reconstruct the hierarchy without creating multiple disjointed trees unless the data dictates it. While recursion often comes to mind immediately, solving this efficiently requires understanding how to traverse the graph from the root downwards or build the structure in a single pass before rendering.

The Graph Theory Perspective

At its core, your data represents a directed acyclic graph (DAG) where every node has exactly one parent, except for the roots which have NULL parents. The most robust approach is to separate the construction phase from the rendering phase. First, you build an internal representation of the tree in memory. Then, you traverse that structure to generate your HTML.

The most efficient way to build this structure in PHP is to iterate through your data exactly once. You need two associative arrays: one to map every node to its parent and another to group children by their parent ID. By separating these concerns, you avoid the performance pitfalls of searching for parents repeatedly.

Here is a practical implementation pattern using standard PHP arrays:

$data = [
    'H' => ['parent' => 'G', 'name' => 'H'],
    'F' => ['parent' => 'G', 'name' => 'F'],
    'G' => ['parent' => 'D', 'name' => 'G'],
    'E' => ['parent' => 'D', 'name' => 'E'],
    'A' => ['parent' => 'E', 'name' => 'A'],
    'B' => ['parent' => 'C', 'name' => 'B'],
    'C' => ['parent' => 'E', 'name' => 'C'],
    'D' => ['parent' => NULL, 'name' => 'D'],
];

$children = [];
$roots = [];

foreach ($data as $nodeId => $node) {
    $parentId = $node['parent'];
    
    // If it's a root node (or the parent doesn't exist in our map yet), initialize the tree bucket
    if ($parentId === null || !isset($children[$parentId])) {
        $roots[$nodeId] = [];
    } else {
        $children[$parentId][$nodeId] = $node['name'];
    }
}

// This loop ensures we handle cases where a child is defined before its parent 
// in the source array, preventing errors during iteration.
foreach ($data as $nodeId => $node) {
    $parentId = $node['parent'];
    if ($parentId !== null) {
        // Ensure the parent bucket exists even if we haven't seen the parent data row yet
        if (!isset($children[$parentId])) {
            $children[$parentId] = [];
        }
        $children[$parentId][$nodeId] = $node['name'];
        
        // If this node is a root, add it to roots list as well
        if ($parentId === null) {
             // Logic handled above, but strictly speaking we just need to ensure roots are identified
        }
    } else {
        // It's a root
        if (!isset($roots[$nodeId])) {
            $roots[$nodeId] = [];
        }
    }
}

The critical optimization here is that we never search for a parent by iterating through the list. We simply look up the parent in our associative array. This reduces complexity from O(n²) to O(n). Once the structure is built, you have an array of roots and a map of children, making it trivial to render the HTML.

Rendering with Recursion

Once the data structures are prepared, generating the <ul> and <li> elements becomes a straightforward recursive task. You iterate through your $roots array, calling a helper function for each one. This helper function takes a list of children, iterates over them, and recursively calls itself on the children of each child.

function renderTree(array $children): string {
    if (empty($children)) {
        return '';
    }

    $html = '<ul>';
    
    foreach ($children as $childName => $data) {
        // Assuming we have a way to get the children of this specific node 
        // from our built structure. For this example, let's assume $children 
        // is actually keyed by ID and contains the name.
        
        // In a real scenario based on the previous logic:
        // We need access to the full tree map to drill down.
        
        // Simplified for explanation:
        $html .= '<li>' . htmlspecialchars($childName) . '</li>';
    }
    
    return $html . '</ul>';
}

However, a more direct recursive approach works if you have a function that accepts a specific node ID and returns its children. You would start by finding all roots (nodes with parent == NULL). Then, for each root, you call the renderer. The renderer looks up the immediate children of that node, renders an <li> for each, and then recursively calls itself on every child found.

Handling Edge Cases and Trade-offs

You mentioned there are no inconsistencies in your pairings, which simplifies things significantly. You don't need to validate circular references or orphan nodes because the data guarantees a valid tree structure. However, you must be mindful of how you initialize your arrays.

A common pitfall is assuming that the order of iteration in your source array matches the depth of the tree. If you try to build the tree by iterating and immediately adding children to a parent, you might encounter a node whose parent hasn't been processed yet if you were strictly relying on the parent being "ready." That is why the two-pass approach (or using a map of all nodes) is superior. It decouples the logical structure from the input order.

Performance-wise, building the adjacency list (the $children map) in memory takes constant time relative to the dataset size if you use hash maps. Rendering the tree is linear with respect to the number of nodes because you visit each node exactly once during the recursion. This ensures your solution scales well even if you have thousands of hierarchical levels or items.

If you are working within a Laravel application, you might consider leveraging Eloquent relationships, but for pure data transformation tasks like this, standard PHP arrays offer zero overhead and maximum clarity. The logic remains identical regardless of the framework, ensuring your code is portable and dependency-free.

Our network