# Count the nodes in a binary tree structure

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:

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:

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 |
+-----------+-------------+-------+
``````
• 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. Aug 22, 2015 at 16:58

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 ║
╚═══════════╩═════════════╩═══════╝
``````