# Implement a Parent-Level Count in Binary Search Tree

Based on this question, have any way to implement a parent level count?

Find highest level of a hierarchical field: with vs without CTEs

Example table:

``````+----+-----------+
| id | parent_id |
+----+-----------+
|  1 |         0 |
|  2 |         1 |
|  3 |         1 |
|  4 |         2 |
|  5 |         2 |
|  6 |         3 |
|  7 |         3 |
|  8 |         5 |
|  9 |         5 |
| 10 |         7 |
+----+-----------+
``````

Function:

``````DELIMITER \$\$

DROP FUNCTION IF EXISTS `junk`.`GetFamilyTree` \$\$
CREATE FUNCTION `junk`.`GetFamilyTree` (GivenID INT, Count INT) RETURNS varchar(1024) CHARSET latin1
DETERMINISTIC
BEGIN

DECLARE rv,q,queue,queue_children VARCHAR(1024);
DECLARE queue_length,front_id,pos INT;

SET rv = '';
SET queue = GivenID;
SET queue_length = 1;
SET count_limit = Count;

WHILE queue_length > 0 && count_limit > 0 DO
SET front_id = FORMAT(queue,0);
IF queue_length = 1 THEN
SET queue = '';
ELSE
SET pos = LOCATE(',',queue) + 1;
SET q = SUBSTR(queue,pos);
SET queue = q;
END IF;
SET queue_length = queue_length - 1;

SELECT IFNULL(qc,'') INTO queue_children
FROM (SELECT GROUP_CONCAT(id) qc
FROM pctable WHERE parent_id = front_id) A;

IF LENGTH(queue_children) = 0 THEN
IF LENGTH(queue) = 0 THEN
SET queue_length = 0;
END IF;
ELSE
IF LENGTH(rv) = 0 THEN
SET rv = queue_children;
ELSE
SET rv = CONCAT(rv,',',queue_children);
END IF;
IF LENGTH(queue) = 0 THEN
SET queue = queue_children;
ELSE
SET queue = CONCAT(queue,',',queue_children);
END IF;
SET queue_length = LENGTH(queue) - LENGTH(REPLACE(queue,',','')) + 1;
END IF;
END WHILE;

RETURN rv;

END \$\$
``````

I need implement a count on that function to limit iterate based on parameter passed on query.

``````SELECT id,parent_id, GetFamilyTree(1, 3) FROM pctable;
``````

Detail: first param is id of desired family tree secund param is a level depth of descendants

Example result of example table:

``````+----+-----------+
| id | parent_id |
+----+-----------+
|   1|        0  |
|   2|        1  |
|   3|        1  |
|   4|        2  |
|   5|        2  |
|   6|        3  |
|   7|        3  |
+----+-----------+
``````

It is possible?

In this case, the count not working as well...its counting every tree item, not every tree level.

• I have a question on the how you want `GetFamilyTree(id,3)` to behave. Do you want `GetFamilyTree(id,3)` to bring back a tree whose height is 3 or do you want the return list liimited by the first three ids in the output ? Nov 28, 2014 at 20:02
• I need to limit in 3 levels of parents, first level is the proper id, secund level has two childrens of id and third level has four childrens of secund level. if secund level has just one children of id, and third level just one children of secund level, function may have return just these three results. Nov 28, 2014 at 20:19
• i have added more details... and adjusted example table for simulate desired result. Nov 28, 2014 at 20:36

If you look at the `GetFamilyTree` code, there is nothing monitoring the tree height or any particular level.

To compensate, I have a revised version of this code

``````DELIMITER \$\$

DROP FUNCTION IF EXISTS `junk`.`GetFamilyTree` \$\$
CREATE FUNCTION `junk`.`GetFamilyTree` (GivenID INT,LevelLimit INT)
RETURNS varchar(1024) CHARSET latin1
DETERMINISTIC
BEGIN
DECLARE rv,q,queue,queue_children,front_rc,level_part VARCHAR(1024);
DECLARE queue_length,front_id,front_ht,pos,curr_level INT;

SET rv = '';
SET queue = CONCAT(GivenID,':0');
SET queue_length = 1;

WHILE queue_length > 0 DO
SET front_id = FORMAT(queue,0);
IF queue_length = 1 THEN
SET front_rc = queue;
SET queue = '';
SET pos = LOCATE(':',front_rc);
ELSE
SET pos = LOCATE(',',queue);
SET front_rc = LEFT(queue,pos - 1);
SET q = SUBSTR(queue,pos + 1);
SET queue = q;
SET pos = LOCATE(':',front_rc);
END IF;
SET front_id = LEFT(front_rc,pos - 1);
SET front_ht = SUBSTR(front_rc,pos + 1);
SET queue_length = queue_length - 1;

SELECT IFNULL(qc,'') INTO queue_children
FROM (SELECT GROUP_CONCAT(CONCAT(id,':',front_ht+1)) qc
FROM pctable WHERE parent_id = front_id) A;

IF LENGTH(queue_children) = 0 THEN
IF LENGTH(queue) = 0 THEN
SET queue_length = 0;
END IF;
ELSE
IF LENGTH(rv) = 0 THEN
IF front_ht < LevelLimit THEN
SET rv = queue_children;
END IF;
ELSE
IF front_ht < LevelLimit THEN
SET rv = CONCAT(rv,',',queue_children);
END IF;
END IF;
IF LENGTH(queue) = 0 THEN
SET queue = queue_children;
ELSE
SET queue = CONCAT(queue,',',queue_children);
END IF;
SET queue_length = LENGTH(queue) - LENGTH(REPLACE(queue,',','')) + 1;
END IF;
END WHILE;

#
# Strip away level parts of the output
#
IF LENGTH(rv) > 0 THEN
SET curr_level = 1;
WHILE curr_level <= LevelLimit DO
SET level_part = CONCAT(':',curr_level);
SET rv = REPLACE(rv,level_part,'');
SET curr_level = curr_level + 1;
END WHILE;
END IF;

RETURN rv;
END \$\$

DELIMITER ;
``````

This is how I changed it: For each id in the queue, I introduce a height.

Each member of the list will look like this:

``````id:height,id:height,id:height, ... ,id:height
``````

I place a limit on when to concatenate by adding `IF front_ht < LevelLimit THEN`

When the list is compiled, I then taken the return value `rv` and remove all colons (`:`) and the number behind each colon. What's left is a comma-separated list of IDs within the height range set by `LevelLimit`. If you want the height to be included in the output, remove the `Strip away level parts of the output` code at the bottom of the Stored Procedure.

Give it a Try !!!

# UPDATE 2014-11-29 16:05 EST

It is important to note that you need to make GROUP_CONCAT have enough space to collect a long list of info. Please run this in mysql:

``````SET GLOBAL group_concat_max_len = 1048576;
SET group_concat_max_len = 1048576;
``````

Then, add this to `my.cnf`

``````[mysqld]
group_concat_max_len =1048576;
``````
• I did not understand , it is necessary to keep ': height' to run the function. I tried removing and stopped working. Nov 29, 2014 at 14:34
• I realized that there is enough loss of performance rather than perform some queries and process the data in php . Do you consider that it is feasible to bring up to 1024 results? Nov 29, 2014 at 14:52