Count the nodes in a binary tree structure

Question

I need to count the left and right nodes in a binary tree structure (output grouped by joiningDate), given a particular starting node parent id (pid).

The tree is stored in the table shown below:

sample data screen shot

For example using pid = 4 you would get 2 cid (5 and 11 ) then you would use those as the new pid (5, 11). When cid is null or the full tree has been traversed count all the placement = L and placement = R. Other placements like "M" should be ignored.

Illustration:

enter image description here

Expected output for a selected starting node of 4:

+-----------+-------------+-------+
| placement | joiningDate | Total |
+-----------+-------------+-------+
| L | 2015年02月02日 | 3 |
| R | 2015年02月02日 | 1 |
| L | 2015年08月21日 | 4 |
| L | 2015年12月12日 | 1 |
+-----------+-------------+-------+

• Andriy M: If you are struggling to explain your problem verbally, please try to additionally provide an example that includes both a data sample and the expected output, where the expected output matches the data sample precisely. And please update your question with that information rather then using comments.

Answer 1

This is most easily implemented in SQL Server using a Recursive Common Table Expression.

Table definition

DECLARE @binaryUser AS TABLE
(
 id integer NOT NULL,
 joiningDate date NOT NULL,
 placement char(1) NOT NULL,
 pId integer NOT NULL,
 cId integer NOT NULL,
 referBy integer NOT NULL
);

Data

INSERT @binaryUser
 (id, joiningDate, placement, pid, cid, referBy)
VALUES
 (4, '20150202', 'L', 4, 5, 4),
 (6, '20150202', 'R', 5, 8, 4),
 (8, '20150202', 'R', 4, 11, 4),
 (9, '20150202', 'L', 5, 10, 4),
 (25, '20151212', 'L', 8, 9, 4),
 (31, '20150821', 'R', 8, 12, 4),
 (33, '20150821', 'R', 12, 13, 4),
 (36, '20150821', 'R', 9, 14, 4),
 (37, '20150821', 'M', 9, 15, 4),
 (38, '20150821', 'L', 10, 16, 4),
 (39, '20150821', 'M', 4, 17, 4);

Solution

This is presented as a script, but it is trivial to convert it to a stored procedure. The basic idea is to traverse the tree recursively, then count the rows found.

DECLARE @pId integer = 4;
-- Recursive CTE
WITH R AS
(
 -- Anchor
 SELECT 
 BU.joiningDate,
 BU.cId,
 BU.placement
 FROM @binaryUser AS BU
 WHERE
 BU.pId = @pId
 AND BU.placement IN ('L', 'R')
 UNION ALL
 -- Recursive part
 SELECT
 BU.joiningDate,
 BU.cId,
 R.placement
 FROM R
 JOIN @binaryUser AS BU
 ON BU.pId = R.cId
 WHERE
 BU.placement IN ('L', 'R')
)
-- Final groups of nodes found
SELECT
 R.placement,
 R.joiningDate,
 Total = COUNT_BIG(*)
FROM R
GROUP BY
 R.placement,
 R.joiningDate
OPTION (MAXRECURSION 0);

SEDE Demo

Output:

╔═══════════╦═════════════╦═══════╗
║ placement ║ joiningDate ║ Total ║
╠═══════════╬═════════════╬═══════╣
║ L ║ 2015年02月02日 ║ 3 ║
║ R ║ 2015年02月02日 ║ 1 ║
║ L ║ 2015年08月21日 ║ 4 ║
║ L ║ 2015年12月12日 ║ 1 ║
╚═══════════╩═════════════╩═══════╝