Count all child nodes of hierarchical data in a table

Question

I want to count number of all child nodes under any level of tree structure maintained in a table using adjacency model (parent-child key). Table structure and data looks like this:

id -  item-   parentid    
1  -  A   -   
2  -  B   -   1   
3  -  C   -   1   
4  -  D   -   2   
5  -  E   -   2   
6  -  F   -   3   
7  -  G   -   3   
8  -  H   -   5   
9  -  I   -   5   
10 -  J   -   9   
11 -  K   -   4   

For example B has following child and grand child structure:

• B
  • E
    • H
    • I
      • J
  • F
    • K

Now if you want to count "All child nodes of B" my answer should be 6.

Any pure SQL Query based solution would be of great help. Or mysql/php will also work.

Thanks!

Answer 1

The way you store your data will not allow for a simple query to get the total child count. But have a look at:

http://en.wikipedia.org/wiki/Nested_set_model

Where a query like this would be possible.

Answer 2

Below is a PHP based solution:

function countChildren($startId) {
    $directDescendents = *_query("SELECT id FROM Table WHERE parentid = ?", array( $startId ));
    $count = *_num_rows($directDescendents);
    while($row = *_fetch_array($directDescendents))
        $count += countChildren($row['id']);
    return $count;
}

$numChildren = countChildren(2); // Number of Children for 'B'

Replace *_num_rows and *_fetch_array with whatever functions for the SQL extension you are using. This won't be as efficient as a pure SQL solution, but it will work. The way I'm querying in the function is assuming bound parameters, but execute the query as you like.