Binary tree count all child nodes in left and right side

Question

                                     1
                                   /   \
                                 2       3
                                / \     / \
                               4   5   6   7
                             /      \       \
                           8          9      11
                          /                   \
                        10                      12
                       /  \
                     13    14

Am having a binary tree like this. Here, 1 is the parent and I wanna count all the children in both left and right side of 1

And I am having the following mysql table structure

**id** **amount** **left** **right**
  1       3000       2        3
  2       3000       4        5
  3       750        6        7
  4       750        8      *null*
  5       3000    *null*      9
  6       750     *null*    *null*
  7       750     *null*      11
  8       750       10      *null*
  9       3000    *null*    *null*
 10       3000      13        14
 11       750     *null*      12
 12       3000    *null*    *null*  
 13       750     *null*    *null*
 14       3000    *null*    *null*

Now I wanna count all the left nodes as well as the right nodes based on the plan amount of the ID's Though am having thousands of data . Is it possible to count all the nodes by differentiating them by the plan amount? For Example if the ID 2 contains 5 IDs ( 4, 8, 10, 13, 14 ) in it's left side and each IDs are of different Plan amount can I count how many IDs under 2 are in 750 plan ?? using php

fiddle

Specify MySQL version - it is critical for your task. Anycase - perform this on the MySQL side, not in PHP. — Akina, Aug 28 '20 at 10:29
MySQL version is 5.6 @Akina Please help me in this!! Thank you — Sam Leumas, Aug 28 '20 at 10:35
Your version does not support CTE - so create stored procedure. — Akina, Aug 28 '20 at 10:36
*For Example if the ID 2 contains 5 IDs ( 4, 8, 10, 13, 14 ) in it's left side and each IDs are of different Plan amount can I count how many IDs under 2 are in 750 plan ?* Please show the result which you need for starting ID = 2. Does you need one output number of total child nodes? or 2 separate numbers - for nodes which are left or right for their parents separately? — Akina, Aug 28 '20 at 10:39
Yeah I need separate count for the left side and for the right side — Sam Leumas, Aug 28 '20 at 10:41
use this answer https://stackoverflow.com/a/33737203/9981798 as a reference. — sachco, Aug 28 '20 at 10:42
@AbhishekSachan This answer (its code for 5+ version) is wrong in general - it needs child row `id` to be greater than its parent `id` strictly. — Akina, Aug 28 '20 at 10:45
*What is stored procedure??* It is static object on MySQL side (a part of database, like a table or a view). Must be created once. — Akina, Aug 28 '20 at 11:05

Akina · Answer 1 · 2020-08-28T11:04:56.687

CREATE PROCEDURE count_nodes (IN id INT, IN amount INT)
BEGIN
CREATE TABLE temp (id INT PRIMARY KEY, amount INT, id_left INT, id_right INT, side INT);
INSERT INTO temp SELECT *, 0 FROM test WHERE test.id = id;
REPEAT
    INSERT IGNORE INTO temp
    SELECT test.*, CASE WHEN test.id = temp.id_left THEN 1 ELSE 2 END FROM test JOIN temp ON test.id IN (temp.id_left, temp.id_right);
UNTIL NOT ROW_COUNT() END REPEAT;
SELECT SUM(side=1) left_childs, SUM(side=2) right_childs FROM temp WHERE temp.amount = amount;
DROP TABLE temp;
END

fiddle

If there is no rows matched starting id or provided amount in id's subtree then the procedure will return NULLs.

The procedure is cycle-safe (do not result to infinite loop on wrong source table's data). But it is not safe to wrong data where id_left = id_right - such wrong nodes will be counted as left.

Binary tree count all child nodes in left and right side

1 Answers1