PHP hierarchical array - Parents and childs

Question

I use PHP and mySQL with Idiorm. That might not be relevant.

My PHP array

• It's a relationship between parents and childs.
• 0 is the root parent.
• Example: Root parent 0 have the child 33 which have the child 27 which have the child 71.

This array structure can be changed if needed for solving the problem.

array (
  33 => 
    array (
      0 => '27',
      1 => '41',
  ),
  27 => 
    array (
      0 => '64',
      1 => '71',
  ),
  0 => 
    array (
      0 => '28',
      1 => '29',
      2 => '33',
  ),
)

My hierarchical result

Something like this, but as an array...

  0 => 
      28
      29
      33
         27 =>
               64
               71
         41

Information

• The depth are unkown and it can be unlimited. I tried foreach, but it might not be the way.

My own thoughts

• Some recursive function?
• Some while loops?

I tried both of the above, just got a mess. It's a brainer.

Answer 1

I had a different problem and could not find a solution that worked for me on this page. I needed to create a tree but without knowing the root id. This means I have to go through my flat array and build branches with the most parently items at the top of the tree.

If anyone else needs to build a tree without a root parent item id, here's how I did it.

<?php

$rows = [
    (object) [
        'id' => 1001,
        'parentid' => 1000,
        'name' => 'test1.1'
    ],
    (object) [
        'id' => 1000,
        'parentid' => 100,
        'name' => 'test1'
    ],
    (object) [
        'id' => 1002,
        'parentid' => 1000,
        'name' => 'test1.2'
    ],
    (object) [
        'id' => 1004,
        'parentid' => 1001,
        'name' => 'test1.1.1'
    ],
    (object) [
        'id' => 1005,
        'parentid' => 1004,
        'name' => 'test1.1.1.1'
    ],
    (object) [
        'id' => 100,
        'parentid' => 10,
        'name' => 'test 0'
    ],
    (object) [
        'id' => 1006,
        'parentid' => 1002,
        'name' => 'test1.2.1'
    ],
    (object) [
        'id' => 1007,
        'parentid' => 1002,
        'name' => 'test1.2.2'
    ],
];

function add_child(stdClass $parent, stdClass $child) {
    if ($child->parentid != $parent->id) {
        throw new Exception('Attempting to add child to wrong parent');
    }

    if (empty($parent->children)) {
        $parent->children = [];
    } else {
        // Deal where already in branch.
        foreach ($parent->children as $idx => $chd) {
            if ($chd->id === $child->id) {
                if (empty($chd->children)) {
                    // Go with $child, since $chd has no children.
                    $parent->children[$idx] = $child;
                    return;
                } else {
                    if (empty($child->children)) {
                        // Already has this child with children.
                        // Nothing to do.
                        return;
                    } else {
                        // Both childs have children - merge them.
                        $chd->children += $child->children;
                        $parent->children[$idx] = $child;
                        return;
                    }
                }
            }
        }
    }

    $parent->children[] = $child;
}

function build_branch(&$branch, &$rows, &$parent = null) {
    $hitbottom = false;
    while (!$hitbottom) {
        $foundsomething = false;
        // Pass 1 - find children.
        $removals = []; // Indexes of rows to remove after this loop.
        foreach ($rows as $idx => $row) {
            if ($row->parentid === $branch->id) {
                // Found a child.
                $foundsomething = true;
                // Recurse - find children of this child.
                build_branch($row, $rows, $branch);
                add_child($branch, $row);
                $removals[] = $idx;
            }
        }
        foreach ($removals as $idx) {
            unset($rows[$idx]);
        }
        // Pass 2 - find parents.
        if ($parent === null) {
            $foundparent = false;
            foreach ($rows as $idx => $row) {
                if ($row->id === $branch->parentid) {
                    // Found parent
                    $foundsomething = true;
                    $foundparent = true;

                    add_child($row, $branch);
                    unset ($rows[$idx]);
                    // Now the branch needs to become the parent since parent contains branch.
                    $branch = $row;
                    // No need to search for other parents of this branch.
                    break;
                }
            }
        }

        $hitbottom = !$foundsomething;
    }
}

function build_tree(array $rows) {
    $tree = [];
    while (!empty($rows)) {
        $row = array_shift($rows);
        build_branch($row, $rows);
        $tree[] = $row;
    }
    return $tree;
}

$tree = build_tree($rows);

print_r($tree);

Answer 2

public function createTree (&$list, $parentId = null) {
    $tree = array();
    foreach ($list as $key => $eachNode) {
        if ($eachNode['parentId'] == $parentId) {
            $eachNode['children'] = $this->createTree ($list,$eachNode['id']);
            $tree[] = $eachNode;
            unset($list[$key]);
        }
    }
    return $tree;
}

In that function pass the associative array and if the most parent is not null then just pass the most parent id as second argument.

Answer 3

great answer from @Jens Törnell, just wanted to add a little improvement that if your parent_id and id is actually string instead of number then above method will fail and after creating children array, it will create those childrens arrays again as separate individual array. In order to fix that you should do triple equal check and by telling data type of variable i.e (string) in comparison.

For string based Id and Parent_id in array

function buildTree(array $elements, $parentId = 0) {
    $branch = array();

    foreach ($elements as $element) {
        if ((string)$element['parent_id']  === (string)$parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[] = $element;
        }
    }

    return $branch;
}

additionally if someone desire, he can add a third parameter to function as well to specify data type of variables dynamically i.e function buildTree(array $elements, $parentId = 0, $datatype='string') but then you will have to take of any other error occur.

hope it will help someone!

Answer 4

I added to @Jens Törnell's answers to enable defining the options for the column name of parent_id, the children array key name, and also the column name for id.

/**
 * function buildTree
 * @param array $elements
 * @param array $options['parent_id_column_name', 'children_key_name', 'id_column_name'] 
 * @param int $parentId
 * @return array
 */
function buildTree(array $elements, $options = [
    'parent_id_column_name' => 'parent_id',
    'children_key_name' => 'children',
    'id_column_name' => 'id'], $parentId = 0)
    {
    $branch = array();
    foreach ($elements as $element) {
        if ($element[$options['parent_id_column_name']] == $parentId) {
            $children = buildTree($elements, $options, $element[$options['id_column_name']]);
            if ($children) {
                $element[$options['children_key_name']] = $children;
            }
            $branch[] = $element;
        }
    }
    return $branch;
}

Since the functionality is quite universal, I managed to use the above function in most of my projects.

Answer 5

The suggestion by @deceze worked. However the input array needs to change a litte, like this...

$rows = array(
    array(
        'id' => 33,
        'parent_id' => 0,
    ),
    array(
        'id' => 34,
        'parent_id' => 0,
    ),
    array(
        'id' => 27,
        'parent_id' => 33,
    ),
    array(
        'id' => 17,
        'parent_id' => 27,
    ),
);

From https://stackoverflow.com/a/8587437/476:

function buildTree(array $elements, $parentId = 0) {
    $branch = array();

    foreach ($elements as $element) {
        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[] = $element;
        }
    }

    return $branch;
}

$tree = buildTree($rows);

print_r( $tree );