Total Recruits Down Each Player's Referral Tree

Hard
197.

Total Recruits Down Each Player's Referral Tree

The "Invite a friend" programme rewards a player for everyone they brought in, directly or indirectly: if Asha invited Ravi and Ravi invited Meera, Meera is one of Asha's recruits too. referred_by points to the inviting player; referral chains are at most four levels deep and never loop.

For every player who referred at least one other player, return gamertag, direct_referrals and total_recruits (all players anywhere below them in the tree), ordered by total_recruits descending, then gamertag.

Tables

Table: Player

ColumnType
player_idint
gamertagvarchar
referred_byint

Primary key: player_id.

referred_by is the player_id of the player whose invite link was used, or NULL for an organic sign-up. Gamertags are unique.

Example

The rows must come back in the order shown.

Player

player_idgamertagreferred_by
1ShadowFangNULL
2PixelPriya1
3LagLord1
4ClutchDiya2
5FrostDev4
6KingKabirNULL
7AceAisha6
8BotSlayer4

Output

gamertagdirect_referralstotal_recruits
ShadowFang25
PixelPriya13
ClutchDiya22
KingKabir11
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

Total Recruits Down Each Player's Referral Tree

The "Invite a friend" programme rewards a player for everyone they brought in, directly or indirectly: if Asha invited Ravi and Ravi invited Meera, Meera is…

  • Difficulty: Hard
  • Topics: Subqueries, Joins, Aggregation
  • Dialect: MySQL
  • Problem: #197

Problem statement

The "Invite a friend" programme rewards a player for everyone they brought in, directly or indirectly: if Asha invited Ravi and Ravi invited Meera, Meera is one of Asha's recruits too. referred_by points to the inviting player; referral chains are at most four levels deep and never loop.

For every player who referred at least one other player, return gamertag, direct_referrals and total_recruits (all players anywhere below them in the tree), ordered by total_recruits descending, then gamertag.

Tables

Table: Player

ColumnType
player_idint
gamertagvarchar
referred_byint

Primary key: player_id.

referred_by is the player_id of the player whose invite link was used, or NULL for an organic sign-up. Gamertags are unique.

Examples

Example 1

Player

player_idgamertagreferred_by
1ShadowFangNULL
2PixelPriya1
3LagLord1
4ClutchDiya2
5FrostDev4
6KingKabirNULL
7AceAisha6
8BotSlayer4

Output

gamertagdirect_referralstotal_recruits
ShadowFang25
PixelPriya13
ClutchDiya22
KingKabir11

How to solve Total Recruits Down Each Player's Referral Tree

The total depends on the whole subtree, which a fixed number of joins only handles if the depth is fixed — the general tool is a recursive CTE. The anchor turns each referral into a pair (ancestor = the inviter, recruit = the player). The recursive member takes every pair found so far and adds the recruit's own referrals with the same ancestor, so ShadowFang → PixelPriya produces ShadowFang → ClutchDiya, then ShadowFang → FrostDev and ShadowFang → BotSlayer. The recursion stops when a level finds no new players; since chains never loop it always ends.

Each pair is one recruit of one ancestor (a tree gives every recruit one path up, so nobody is counted twice), so COUNT(*) grouped by ancestor is total_recruits. The direct referrals are a correlated count of players whose referred_by is that ancestor — or, in the pair table, the pairs whose recruit points straight at the ancestor. Players who invited nobody have no pairs and do not appear.

With the depth capped at four, the same pairs come from a UNION ALL of self joins one to four levels deep, which is what the recursion unrolls into. The recursive form keeps working if the cap is ever lifted; the cost is one join per level.

Reference solution (MySQL)

WITH RECURSIVE chain (ancestor_id, recruit_id) AS (
  SELECT referred_by, player_id FROM Player WHERE referred_by IS NOT NULL
  UNION ALL
  SELECT c.ancestor_id, p.player_id
  FROM chain c
  JOIN Player p ON p.referred_by = c.recruit_id
)
SELECT a.gamertag,
       (SELECT COUNT(*) FROM Player d WHERE d.referred_by = a.player_id) AS direct_referrals,
       COUNT(*) AS total_recruits
FROM chain c
JOIN Player a ON a.player_id = c.ancestor_id
GROUP BY a.player_id, a.gamertag
ORDER BY total_recruits DESC, a.gamertag

Another way

WITH pairs AS (
  SELECT p1.referred_by AS ancestor_id, p1.player_id AS recruit_id FROM Player p1 WHERE p1.referred_by IS NOT NULL
  UNION ALL
  SELECT p1.referred_by, p2.player_id FROM Player p1 JOIN Player p2 ON p2.referred_by = p1.player_id WHERE p1.referred_by IS NOT NULL
  UNION ALL
  SELECT p1.referred_by, p3.player_id FROM Player p1 JOIN Player p2 ON p2.referred_by = p1.player_id JOIN Player p3 ON p3.referred_by = p2.player_id WHERE p1.referred_by IS NOT NULL
  UNION ALL
  SELECT p1.referred_by, p4.player_id FROM Player p1 JOIN Player p2 ON p2.referred_by = p1.player_id JOIN Player p3 ON p3.referred_by = p2.player_id JOIN Player p4 ON p4.referred_by = p3.player_id WHERE p1.referred_by IS NOT NULL
)
SELECT a.gamertag,
       SUM(CASE WHEN r.referred_by = a.player_id THEN 1 ELSE 0 END) AS direct_referrals,
       COUNT(*) AS total_recruits
FROM pairs x
JOIN Player a ON a.player_id = x.ancestor_id
JOIN Player r ON r.player_id = x.recruit_id
GROUP BY a.player_id, a.gamertag
ORDER BY total_recruits DESC, a.gamertag

← New-Player Funnel From Install to First Purchase by Platform · Lab Reports Breaching the 24-Hour Turnaround →