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);
