Count the nodes in a binary tree structure
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 ║
╚═══════════╩═════════════╩═══════╝