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:

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 |
+-----------+-------------+-------+

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