PHP build tree BUT multiple parents in an array

Question

I suffered for days looking for an answer and trying to solve the problme myself but I could not.

I have data in a PHP array with a the key parent_id as an array. I found how to build a tree but only if it has only ONE parent! But in my case it has multiple parents and it must be nested below every parent.

Here is an example:

Parents

array( 'id' => 1, 'name' => 'Parent 1', 'parent_id' => array() );

array( 'id' => 2, 'name' => 'Parent 2', 'parent_id' => array() );

Children

array( 'id' => 3, 'name' => 'Child 1', 'parent_id' => array(1, 2) );

I want the tree to be built like so:

array( 'id' => 1, 'name' => 'Parent 1', 'parent_id' => array(), 'children' => array( array( 'id' => 3, 'name' => 'Child 1', 'parent_id' => array(1, 2) ) ), ); array( 'id' => 2, 'name' => 'Parent 2', 'parent_id' => array(), 'children' => array( array( 'id' => 3, 'name' => 'Child 1', 'parent_id' => array(1, 2) ) ), );

Can you suggest a working function that may help me. Thanks in advance.

EDITED (DEMO)

@Jeff Lambert is right. What I did was to loop through elements and if any has parents, I add its ID to a newly created key children .. This way I can retrieve it whenever I want.

function build_tree(array $elements)
{
    $indexed = array();
    foreach($elements as $element)
    {
        $element = (array) $element;
        $indexed[$element['id']] = $element;
    }

    $elements = $indexed;
    unset($indexed, $element);

    foreach($elements as $id => $element)
    {
        if ( ! empty($element['parent_id']))
        {
            foreach($element['parent_id'] as $parent)
            {
                if (isset($elements[$parent]))
                {
                    $elements[$parent]['children'][] = $element['id'];
                }
            }
        }
    }

    return $elements;
}

Then I only need to create and little function to retrieve element details like so:

function get_element($id, $return = NULL)
{
    // Check the element inside the array
    if (isset($elements[$id])
    {
        // In case I want to return a single value
        if ($return !== NULL and isset($elements[$id][$return])
        {
            return $elements[$id][$return];
        }
        return $elements[$id];
    }
    return FALSE; // Or NULL, as you wish
}

Answer 1

Update

If you want/need to nest the nodes (eg a parent can have 1 or more child nodes, while at the same time be a child node of another parent), then the easiest approach would be to assign references to nodes.

I've hacked together a quick demo that is almost identical to my original approach, apart from that it uses references instead of assigning by value. The code looks like this:

function buildTree(array $data)
{
    $data = array_column($data, null, 'id');
    //reference to each node in loop
    foreach ($data as &$node) {
        if (!$node['parent_id']) {
            //record has no parents - null or empty array
            continue; //skip
        }
        foreach ($node['parent_id'] as $id) {
            if (!isset($data[$id])) { // make sure parent exists
                throw new \RuntimeException(
                    sprintf(
                        'Child id %d is orphaned, no parent %d found',
                        $node['id'], $id
                    )
                );
            }
            if (!isset($data[$id]['children']) {
                $data[$id]['children'] = array();
            }
            $data[$id]['children'][] = &$node; //assign a reference to the child node
        }
    }
    return $data;
}

The double reference is required here, because if you did not use the foreach ($data as &$node), the $node variable would be a copy of the original node. Assigning a reference to the copy wouldn't do you any good. In fact, it'd produce the wrong results.

Likewise, if you did not assign a reference to the &$node from the loop, you'd not get the full list of child nodes throughout the tree.
It's not the easiest thing to explain, but the net result speaks for itself: using the references here allows you to build the tree in full in a single function call.

---

Here's what I'd do. First, I'd use the id's as array keys, so I can more easily find the parents for each child:

$parents = array_column($parents, null, 'id');

if you're on an older version of PHP, and can't upgrade, this is the equivalent of writing:

$indexed = array();
foreach ($parents as $parent) {
    $indexed[$parent['id']] = $parent;
}
$parents = $indexed;

Now iterate over the children, and assign them to their parents:

foreach ($children as $child) {
    foreach ($child['parent_id'] as $id) {
        if (!isset($parents[$id]['children']) {
            $parents[$id]['children'] = array();//ensure the children key exists
        }
        $parents[$id]['children'][] = $child;//append child to parent
    }
}

It really doesn't matter if $parents and $children are 2 separate arrays, or both records are in one big array here.

So a function in case the parent and children are in separate arrays would look like this:

function buildTree(array $parents, array $children)
{
    $parents = array_column($parents, null, 'id');
    foreach ($children as $child) {
        foreach ($child['parent_id'] as $id) {
            if (!isset($parents[$id])) { // make sure parent exists
                throw new \RuntimeException(
                    sprintf(
                        'Child id %d is orphaned, no parent %d found',
                        $child['id'], $id
                    )
                );
            }
            if (!isset($parents[$id]['children']) {
                $parents[$id]['children'] = array();
            }
            $parents[$id]['children'][] = $child;
        }
    }
    return $parents;
}

If all of the data is in a single array, then the function will look pretty much the same:

function buildTree(array $data)
{
    $data = array_column($data, null, 'id');
    foreach ($data as $node) {
        if (!$node['parent_id']) {
            //record has no parents - null or empty array
            continue; //skip
        }
        foreach ($node['parent_id'] as $id) {
            if (!isset($data[$id])) { // make sure parent exists
                throw new \RuntimeException(
                    sprintf(
                        'Child id %d is orphaned, no parent %d found',
                        $node['id'], $id
                    )
                );
            }
            if (!isset($data[$id]['children']) {
                $data[$id]['children'] = array();
            }
            $data[$id]['children'][] = $node;
        }
    }
    return $data;
}

Answer 2

that's how it gonna work correctly.

 $arr = array(
      array('id'=>100, 'parentid'=>0, 'name'=>'a'),
      array('id'=>101, 'parentid'=>100, 'name'=>'a'),
      array('id'=>102, 'parentid'=>101, 'name'=>'a'),
      array('id'=>103, 'parentid'=>101, 'name'=>'a'),
    );

    $new = array();
    foreach ($arr as $a){
        $new[$a['parentid']][] = $a;
    }
    $tree = createTree($new, array($arr[0]));
    print_r($tree);

    function createTree(&$list, $parent){
        $tree = array();
        foreach ($parent as $k=>$l){
            if(isset($list[$l['id']])){
                $l['children'] = createTree($list, $list[$l['id']]);
            }
            $tree[] = $l;
        } 
        return $tree;
    }

Answer 3

The solution using in_array function:

// $parents and $children are arrays of 'parents' and 'children' items respectively
$tree = [];
foreach ($parents as $p) {
    $treeItem = $p + ['children' => []];
    foreach ($children as $c) {
        if (in_array($p['id'], $c['parent_id']))
            $treeItem['children'][] = $c;
    }
    $tree[] = $treeItem;
}

print_r($tree);

DEMO link

Answer 4

A tree where each node can have multiple parents is not a tree, but a graph. One way to represent a graph is via an adjacency list.

As it is, you're storing the 'children' of each node within that node index, and you shouldn't because each node will be duplicated the same number of times as other nodes it is connected to. Each node should be represented at the top level of your structure, and contain references to the other nodes they happen to be connected to, in your case your 'parent_id' index. I would separate out the actual definitions of your nodes and declare what other nodes each one is connected to in separate structures.

Something along these lines for defining your nodes:

array(
    0 => array(
        'id'        => 1,
        'name'      => 'Parent 1',
    ),
    1 => array(
        'id'        => 2,
        'name'      => 'Parent 2',
    ),
    2 => array(
        'id'        => 3,
        'name'      => 'Child 1',
    ),
)

And then a separate array looking something like this for defining the connections between nodes:

array(
    // These indices match the node indices above, and the values are the list of 
    // node indices each node has a connection to.
    0 => array(2),
    1 => array(2),
    2 => array(0, 1),
)

Then it should be easy to find and implement any sort of traversal algorithm you may need.

Answer 5

$data = [
        ['id' => 1, 'parent' => []],
        ['id' => 2, 'parent' => [1]],
        ['id' => 3, 'parent' => [2,4]],
        ['id' => 4, 'parent' => []]
    ];

$result = [];

foreach ($data as $item) {
    if(!count($item['parent'])) {
        makeTree($result, $item, $data);
    }
}

print_r($result);

function makeTree(&$result, $item, $data) {
    $result['children'][$item['id']]['data'] = $item;
    if(haveChildren($item['id'], $data)) {
        foreach(children($item['id'], $data) as $child) {
            makeTree($result['children'][$item['id']], $child, $data);
        }
    }
}

function children($id, $data){
    $result = [];
    foreach($data as $item) {
        if(in_array($id, $item['parent'])) {
            $result[] = $item;
        }
    }
    return $result;
}

function haveChildren($id, $data) {
    foreach($data as $item) {
        if(in_array($id, $item['parent'])) {
            return true;
        }
    }
}