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

I have a bunch of name-parentname pairs, that I’d like to turn into as few heirarchical tree structures as possible. So for example, these could be the pairings:

Child : Parent
    H : G
    F : G
    G : D
    E : D
    A : E
    B : C
    C : E
    D : NULL

Which needs to be transformed into (a) heirarchical tree(s):

D
├── E
│   ├── A
│   │   └── B
│   └── C   
└── G
    ├── F
    └── H

The end result that I want is a nested set of <ul> elements, with each <li> containing the child’s name.

There are no inconsistencies in the pairings (child is it’s own parent, parent is child’s child, etc), so a bunch of optimizations can probably be made.

How, in PHP, would I go from an array containing child=>parent pairs, to a set of Nested <ul>s?

I have a feeling that recursion is involved, but I’m not quite awake enough to think it through.

Answer

This requires a very basic recursive function to parse the child/parent pairs to a tree structure and another recursive function to print it out. Only one function would suffice but here’s two for clarity (a combined function can be found at the end of this answer).

First initialize the array of child/parent pairs:

$tree = array(
    'H' => 'G',
    'F' => 'G',
    'G' => 'D',
    'E' => 'D',
    'A' => 'E',
    'B' => 'C',
    'C' => 'E',
    'D' => null
);

Then the function that parses that array into a hierarchical tree structure:

function parseTree($tree, $root = null) {
    $return = array();
    # Traverse the tree and search for direct children of the root
    foreach($tree as $child => $parent) {
        # A direct child is found
        if($parent == $root) {
            # Remove item from tree (we don't need to traverse this again)
            unset($tree[$child]);
            # Append the child into result array and parse its children
            $return[] = array(
                'name' => $child,
                'children' => parseTree($tree, $child)
            );
        }
    }
    return empty($return) ? null : $return;    
}

And a function that traverses that tree to print out an unordered list:

function printTree($tree) {
    if(!is_null($tree) && count($tree) > 0) {
        echo '<ul>';
        foreach($tree as $node) {
            echo '<li>'.$node['name'];
            printTree($node['children']);
            echo '</li>';
        }
        echo '</ul>';
    }
}

And the actual usage:

$result = parseTree($tree);
printTree($result);

Here’s the contents of $result:

Array(
    [0] => Array(
        [name] => D
        [children] => Array(
            [0] => Array(
                [name] => G
                [children] => Array(
                    [0] => Array(
                        [name] => H
                        [children] => NULL
                    )
                    [1] => Array(
                        [name] => F
                        [children] => NULL
                    )
                )
            )
            [1] => Array(
                [name] => E
                [children] => Array(
                    [0] => Array(
                        [name] => A
                        [children] => NULL
                    )
                    [1] => Array(
                        [name] => C
                        [children] => Array(
                            [0] => Array(
                                [name] => B
                                [children] => NULL
                            )
                        )
                    )
                )
            )
        )
    )
)

---

If you want a bit more efficiency, you can combine those functions into one and reduce the number of iterations made:

function parseAndPrintTree($root, $tree) {
    $return = array();
    if(!is_null($tree) && count($tree) > 0) {
        echo '<ul>';
        foreach($tree as $child => $parent) {
            if($parent == $root) {                    
                unset($tree[$child]);
                echo '<li>'.$child;
                parseAndPrintTree($child, $tree);
                echo '</li>';
            }
        }
        echo '</ul>';
    }
}

You’ll only save 8 iterations on a dataset as small as this but on bigger sets it could make a difference.