Reshare Cascades: Size, Depth and Unique Resharers
A reshare points at the post it reshared, which may itself be a reshare, so every original post (one with reshare_of NULL) roots a cascade.
- Difficulty: Hard
- Topics: Subqueries, Aggregation, Joins
- Dialect: MySQL
- Problem: #445
Problem statement
A reshare points at the post it reshared, which may itself be a reshare, so every original post (one with reshare_of NULL) roots a cascade. For each original post with at least one reshare anywhere in its cascade, report total_reshares (every reshare below it, at any level), max_depth (a direct reshare is depth 1, a reshare of that is depth 2, and so on) and unique_resharers (distinct authors of those reshares).
Return the columns post_id, total_reshares, max_depth and unique_resharers, ordered by total_reshares descending, then post_id.
Tables
Table: posts
| Column | Type |
|---|---|
| post_id | int |
| author_id | int |
| reshare_of | int |
| posted_at | datetime |
Primary key: post_id.
reshare_of is the post_id this post reshared (always an earlier post, so there are no cycles), or NULL for an original post.
Examples
Example 1
posts
| post_id | author_id | reshare_of | posted_at |
|---|---|---|---|
| 1 | 10 | NULL | 2025-09-01 10:00:00 |
| 2 | 11 | 1 | 2025-09-01 10:20:00 |
| 3 | 12 | 2 | 2025-09-01 11:00:00 |
| 4 | 11 | 3 | 2025-09-01 12:30:00 |
| 5 | 13 | 1 | 2025-09-01 13:00:00 |
| 6 | 14 | NULL | 2025-09-02 08:00:00 |
| 7 | 10 | 6 | 2025-09-02 09:15:00 |
| 8 | 15 | NULL | 2025-09-02 19:00:00 |
Output
| post_id | total_reshares | max_depth | unique_resharers |
|---|---|---|---|
| 1 | 4 | 3 | 3 |
| 6 | 1 | 1 | 1 |
How to solve Reshare Cascades: Size, Depth and Unique Resharers
Reshares form a forest: each original post is a root and each reshare points at its parent. A cascade can be any number of levels deep, so the query needs recursion. The anchor of WITH RECURSIVE selects the originals, labelling each with itself as root_id and depth 0; the recursive step joins the posts whose reshare_of is a row already found, copying the root and adding 1 to the depth. Because every reshare points at an earlier post, there are no cycles and the recursion stops when a level finds no children.
Each reshare then appears exactly once, tagged with its root and depth. Removing the depth-0 anchors and grouping by root gives the three numbers: COUNT(*) reshares, MAX(depth), and COUNT(DISTINCT author_id) — someone resharing twice in one cascade counts once. Originals nobody reshared have no rows left after the filter and disappear, as asked.
The alternative walks upwards instead: starting from every reshare, it follows reshare_of until it reaches a post that is an original; the row where the ancestor is an original carries the reshare's depth and its root. Both visit each (reshare, ancestor) pair at most once — linear in the total depth of the forest.
Reference solution (MySQL)
WITH RECURSIVE reshare_tree AS (
SELECT post_id AS root_id, post_id, author_id, 0 AS depth
FROM posts WHERE reshare_of IS NULL
UNION ALL
SELECT c.root_id, p.post_id, p.author_id, c.depth + 1
FROM reshare_tree c JOIN posts p ON p.reshare_of = c.post_id
)
SELECT root_id AS post_id,
COUNT(*) AS total_reshares,
MAX(depth) AS max_depth,
COUNT(DISTINCT author_id) AS unique_resharers
FROM reshare_tree
WHERE depth > 0
GROUP BY root_id
ORDER BY total_reshares DESC, post_idAnother way
WITH RECURSIVE up AS (
SELECT post_id AS node, author_id, reshare_of AS ancestor, 1 AS depth
FROM posts WHERE reshare_of IS NOT NULL
UNION ALL
SELECT u.node, u.author_id, p.reshare_of, u.depth + 1
FROM up u JOIN posts p ON p.post_id = u.ancestor
WHERE p.reshare_of IS NOT NULL
)
SELECT r.post_id, COUNT(*) AS total_reshares, MAX(u.depth) AS max_depth, COUNT(DISTINCT u.author_id) AS unique_resharers
FROM up u JOIN posts r ON r.post_id = u.ancestor AND r.reshare_of IS NULL
GROUP BY r.post_id
ORDER BY total_reshares DESC, r.post_id← First-Week Retention by Sign-Up Month · Median Likes per Creator →