Count all Children of Nodes in a Hierarchical (Tree) Data Structure in MySQL using PHP

Question

I want to count the number of all children in any level of a Tree Structure. The Tree isn't binary, so a node can have more than 2 children. Right now I have created a recursive function that does that job, but it is really slow. I need a faster way, but I can't do it in any other way.

So, let's say we have that table:

NodeID |  ParentID
-------------------
  1    |     0
  2    |     1
  3    |     1
  4    |     2
  5    |     1
  6    |     2
  7    |     3
  8    |     5
  9    |     6
 10    |     8
 11    |     6
 11    |     6

• 1
  • 2
    • 4
    • 6
      • 9
      • 11
      • 12
  • 3
    • 7
  • 5
    • 8
      • 10

So, if I want to get the children number of node 1, the number should be 11 instead of 3. The same thing for Node 2. The number should be 5 instead of 2.

This is the Recursive function I have created in PHP, but it is SLOW:

function count_all_nodes($connection, $element_id, $elements=false, $i=0) {
    if (!$elements) {
        $result = mysqli($connection, "SELECT `node_id`, `parent_id` FROM `elements`");

        while ($row = mysqli_fetch_array($result)) {
            $sub_elements["node_id"] = $row["node_id"];
            $sub_elements["parent_id"] = $row["parent_id"];
            $elements[] = $sub_elements;
        }
    }

    foreach ($elements as $element) {
        if ($element["parent_id"] == $element_id) {
            $i++;
            $i += count_all_nodes($connection, $element_id, $elements);
        }
    }

    return $i;
}

Is there any way I can avoid this recursive function?

Thank you!

Answer 1

I think hierarchical data structure (tree) is synonymous of recursion.

I implement two recursive function in php that maybe are faster than your code, because I only execute one MySql query to get the tree information, not one in each call to the recursive function like you.

Example data:

The root node (tree's first node) doesn't have a father, I indicated this setting into its father field '0-A' (this node doesn't exist), but you can put null instead.

To get the tree information I execute this query:

SELECT node, father
FROM tree
ORDER BY node;

I get something like this in php:

$nodes = array ( 0 => array ( 'node' => '1-A', 'father' => '0-A', ), 1 => array ( 'node' => '2-A', 'father' => '1-A', ), 2 => array ( 'node' => '3-A', 'father' => '1-A', ), 3 => array ( 'node' => '4-A', 'father' => '2-A', ), 4 => array ( 'node' => '5-A', 'father' => '2-A', ), 5 => array ( 'node' => '6-A', 'father' => '3-A', ), 6 => array ( 'node' => '7-A', 'father' => '3-A', ), 7 => array ( 'node' => '9-A', 'father' => '6-A', ), 8 => array ( 'node' => '10-A', 'father' => '7-A', ), 9 => array ( 'node' => '8-A', 'father' => '7-A', ), 10 => array ( 'node' => '11-A', 'father' => '10-A', ), )

This is my php code:

/**
 * Count all Children of each node in a Hierarchical Data Structure (Tree).
 *
 * @param array(idNode => idNodeFather) $nodes
 * @param string $actualNode
 * @param array(idDode => totalChildrens) $result
 */
function countChildrensNode($nodes, $actualNode, &$result) {
    foreach($nodes as $node => $father) {
        if($actualNode == $father) {
            $result[$father]++;
            countChildrensNode($nodes, $node, $result);
            incrementActualNodeAncestor($nodes, $father, $result);
        }
    }
}

/**
 * Increment by one to all actual node's ancestors.
 *
 * @param array(idNode => idNodeFather) $nodes
 * @param string $actualNode
 * @param array(idDode => totalChildrens) $result
 */
function incrementActualNodeAncestor($nodes, $actualNode, &$result) {
    foreach($nodes as $node => $father) {
        if($actualNode == $node) {
            if($father != '0-A' && ! is_null($father)) {
                $result[$father]++;
                incrementActualNodeAncestor($nodes, $father, $result);
            }
        }
    }
}

//$nodes is the array return by my query.
$nodesfathers = array_combine (array_column($nodes, "node"), array_column($nodes, "father"));
$res = array_fill_keys(array_column($nodes, "node"), 0);

countChildrensNode($nodesfathers, array_keys($nodesfathers)[0], $res);

countChildrensNode function search forward (increment by one the actual node's father and call incrementActualNodeAncestor the second recursive function) and incrementActualNodeAncestor look for backward (and increment by one each ancestor of the actual node).

The result is in $res var:

'1-A'	10
'2-A'	2
'3-A'	6
'4-A'	0
'5-A'	0
'6-A'	1
'7-A'	3
'9-A'	0
'10-A'	1
'8-A'	0
'11-A'	0