Recursive function to generate multidimensional array and count nested children

Question

I had to recursively generate a multidimensional array and found a way to do it here: Recursive function to generate multidimensional array from database result

However I now need to also count the amount of children every parent has and I don't know how will I adopt the function below to accomplish that?

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

foreach ($elements as $key => $element) {
    if ($element['parent'] == $parentId) {
        $children = generateCorrectArray($elements, $element['category_id']);
        if ($children) {
            $element['children'] = $children;
        }
        $branch[$element['category_id']] = $element;
    }
}

return $branch;
}

EDIT

Array i start with:

$someArray = array(
array(
    "id"=> 1,
    "name"=> "somename1",
    "parent"=> 0,
    "childrenCount" => 0,
    "children" => 0
 ),
array(
    "id"=> 53,
    "name"=> "somename2",
    "parent"=> 1,
    "childrenCount" => 0,
    "children" => 0
),
array(
     "id"=> 921,
    "name"=> "somename3",
    "parent"=> 53,
    "childrenCount" => 0,
    "children" => 0
)

Current function Results

$someArray = array(
array(
"id"=> 1,
"name"=> "somename1",
"parent"=> 0,
"children" => array(
    array(
        "id"=> 53,
        "name"=> "somename2",
        "parent"=> 1,
        "children" => array(
            array(
                "id"=> 921,
                "name"=> "somename3",
                "parent"=> 53,
                "children" => array(

                )
            )
        )
    )
)
)

I would like it to also have a count for each of the nested children.

The goal

$someArray = array(
array(
"id"=> 1,
"name"=> "somename1",
"parent"=> 0,
"childrenCount"=> 2,
"children" => array(
    array(
        "id"=> 53,
        "name"=> "somename2",
        "parent"=> 1,
        "childrenCount"=> 1,
        "children" => array(
            array(
                "id"=> 921,
                "name"=> "somename3",
                "parent"=> 53,
                "childrenCount"=> 0,
                "children" => array(

                )
            )
        )
    )
)
)

Will B. · Accepted Answer · 2021-02-11T06:52:09.177

One of the issues with working with recursive arrays and recordsets is that unless you are just displaying the results you end up rewriting a lot of code to be able to manipulate the data. For example if you remove a child, you have to iterate over the entire array in order to update the rest of the tree, or writing another function to flatten the array tree to iterate over and retrieve the node properties. What happens if you need to find the depth or the root node of a particular node instead of just the number of children?

Try an object to store your tree which can keep track of inheritance and execute functionality that arrays can't. This will make working with the recordsets easier and less time consuming when trying to figure out recursion and if you need to add functionality to it.

Here is an example of what I have used in the past before writing an ORM. https://3v4l.org/PgqlG

I designed it to be able to iterate over the entire tree (flat array), a single node, or a node's children. I also needed the child count, how far down the node was in the tree (depth), and to be able to find the root node. Hope it helps.

/**
 * Provides a flat list of all the nodes
 * Eases with modifying the tree inheritance by id
 */
class NodeList
{

    public $length = 0;

    /**
     * @param mixed $index
     * @return Node|null
     */
    public function item($index)
    {
        $tmp = (array) $this;
        $this->length = count($tmp) - 1;
        if (false === isset($this->$index)) {
            return null;
        }

        return $this->$index;
    }

}

/**
 * Establish and maintain the tree view of each node/child
 */
class Tree extends NodeList
{

    /**
     * Requires id, parent from record set
     * @param null|array|object $recordSet
     */
    public function __construct($recordSet = null)
    {
        if (null !== $recordSet) {
            $this->setChildren($recordSet);
        }
    }

    /**
     * @param array|object $recordSet
     */
    private function setChildren($recordSet)
    {
        foreach ($recordSet as $record) {
            if (true === is_array($record)) {
                $record = (object) $record;
            }
            if (true === isset($record->id)) {
                $this->length++;
                $this->appendNode($record->id, $record);
            }
        }
        foreach ($this as $node) {
            if (false === $node instanceof Node) {
                continue;
            }
            if (false === empty($node->parent) && true === isset($this->{$node->parent})) {
                $children = &$this->{$node->parent}->children;
                $children->length++;
                $children->{$node->id} = &$this->{$node->id};
                $this->item($node->id);
            }
        }
    }

    /**
     * @param string $id
     * @param null|array|object $data
     * @return mixed
     */
    public function appendNode($id, $data = null)
    {
        $this->$id = new Node($data);

        return $this->item($id);
    }

    /**
     * @param string $id
     * @return \Node
     */
    public function getNode($id)
    {
        $item = $this->item($id);
        if (true === empty($item)) {
            $this->appendNode($id, null);
        }

        return $item;
    }

    /**
     * @param string $id
     * @return \Node|null
     */
    public function getParent($id)
    {
        if (null === $this->getNode($id)->parent) {
            return null;
        }

        return $this->getNode($this->getNode($id)->parent);
    }

    /**
     * @param string $id
     * @return int
     */
    public function getDepth($id)
    {
        $i = 0;
        $item = $this->item($id);
        if (null !== $item && null !== $item->parent) {
            $i = $this->getDepth($item->parent) + 1;
        }
        $item->depth = $i;

        return $item->depth;
    }

    /**
     * @param string $id
     */
    public function removeNode($id)
    {
        $this->removeChildren($id);
        if (null !== $this->item(id)) {
            $parent = false;
            if ($this->item($id)->parent) {
                $parent = $this->getParent($id);
            }
            $this->$id = null;
            if ($parent && $parent->children) {
                unset($parent->children->$id);
                $parent->children->length--;
            }
        }
    }

}

/**
 * Single Node
 * This is an overloaded class
 */
class Node
{

    public $id;

    public $name;

    public $parent;

    public $depth;

    public $children;

    /**
     * @param array|object $data
     */
    public function __construct($data)
    {
        $this->children = new NodeList();
        if (null === $data) {
            return;
        }
        foreach ($data as $key => $value) {
            /* I escaped these values since they are redundant to this script */
            switch ($key) {
                case 'children':
                case 'depth':
                case 'childrenCount':
                    continue 2;
            }
            $this->$key = $value;
        }
    }

    /**
     * @return int
     */
    public function countChildren()
    {
        return $this->children->length;
    }

    /**
     * @return \NodeList
     */
    public function getChildren()
    {
        return $this->children;
    }

    public function removeChildren()
    {
        if (null !== $this->getChildren()) {
            foreach ($this->children as $child) {
                if (true === isset($child->children)) {
                    $child->removeChildren();
                }
                $child = null;
            }
        }
        $this->children = null;

        return $this;
    }

}

@Neil_Tinkerer Thanks, I updated the example to the preferred fiddle site and updated the code to be PHP 5.0.2 - 8.0 compatible. Please keep in mind this was written almost a decade ago, so there are some significant changes that could be made to improve the code base and adhere to the current standards. — Will B., Feb 11 '21 at 06:58

score 0 · Answer 2 · answered Jun 03 '13 at 15:48

Try This:

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

foreach ($elements as $key => $element) {
    if ($element['parent'] == $parentId) {
        $children = generateCorrectArray($elements, $element['category_id']);
        if ($children) {
            $element['children'] = $children;
            if(array_key_exists('childrenCount', $element)) {
                $element['childrenCount'] = $element['childrenCount'] + 1;
            } else {
                $element['childrenCount'] = 1;
            }

        }
        $branch[$element['category_id']] = $element;
    }
}

return $branch;
}

can you paste an example input array so that i can run some tests on my machine... — Roshan Gautam, Jun 03 '13 at 16:06

score 0 · Answer 3 · answered Jun 03 '13 at 15:49

/*
    Gets reversed array,
    Returns multidimensional tree array.
*/
function buildTree($parts) {
    if (count($parts) == 1) {
        return $parts[0];
    }
    $last_item = array_pop($parts);
    $last_item['childrenCount'] = count($parts);
    $last_item['children'] = buildTree($parts);
    return $last_item;
}

Tested & working :)

Example:

$parts = array(
            array('1','2','3',5),
            array('3','8','3',1),
            array('1', 5,'2','3'),
            array('D','2','3',5),
            array('A','2','3',5)
        );

var_dump(buildTree(array_reverse($parts)));

Results:

array(6) { [0]=> string(1) "1" [1]=> string(1) "2" [2]=> string(1) "3" [3]=> int(5) ["childrenCount"]=> int(4) ["children"]=> array(6) { [0]=> string(1) "3" [1]=> string(1) "8" [2]=> string(1) "3" [3]=> int(1) ["childrenCount"]=> int(3) ["children"]=> array(6) { [0]=> string(1) "1" [1]=> int(5) [2]=> string(1) "2" [3]=> string(1) "3" ["childrenCount"]=> int(2) ["children"]=> array(6) { [0]=> string(1) "D" [1]=> string(1) "2" [2]=> string(1) "3" [3]=> int(5) ["childrenCount"]=> int(1) ["children"]=> array(4) { [0]=> string(1) "A" [1]=> string(1) "2" [2]=> string(1) "3" [3]=> int(5) } } } } }

That actually killed my Apache, and did not do anything, thank you though — Neta Meta, Jun 03 '13 at 15:59

Recursive function to generate multidimensional array and count nested children

3 Answers3