5

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 |
+-----------+-------------+-------+
  • 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. – Andriy M Aug 22 '15 at 16:58
12

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.