Detect Cycles in a Parent Hierarchy Safely
Start an upward recursive walk from every hierarchy_nodes row. Detect the first repeated node in each origin path without looping forever. Return origin_id, repeated_node_id, repeated_node_name, depth, visited_path — ordered by origin_id.
- Recursive CTE
- Joins
- Subqueries
- CASE expressions
- Type conversion
Exercise brief
Understand the request
Data reliability engineer A hierarchy ingestion gate must expose cycles without hanging, including cycles disconnected from any valid root.
Return
- Return each cyclic origin, repeated node, depth, and visited path.
- Order by origin_id.
Constraints
- Anchor a walk from every node.
- Stop expanding after a repeated ID.
- Use delimiter-safe path membership plus a depth guard.
Data you will use
Review the relevant tables before deciding how to join, filter, or aggregate them.
hierarchy_nodes
node_idINTEGERnode_nameTEXTparent_idINTEGER
Hints, when you need them
Open one clue at a time so you still do the reasoning.
Hint 1
A root-only anchor cannot see a disconnected cycle, so seed one walk per node.
Hint 2
Carry a comma-delimited visited_path and test the next parent with LIKE '%,' || id || ',%'.
Hint 3
Emit the repeated row with is_cycle = 1, then prevent that row from recursing again; retain a defensive depth limit.
Verified SQL answer
Attempt the problem first, then compare structure and reasoning—not just syntax.
Reveal solution and explanation
WITH RECURSIVE walk AS (SELECT node_id AS origin_id, node_id, node_name, parent_id, 0 AS depth, ',' || CAST(node_id AS TEXT) || ',' AS visited_path, 0 AS is_cycle FROM hierarchy_nodes UNION ALL SELECT w.origin_id, p.node_id, p.node_name, p.parent_id, w.depth + 1, w.visited_path || CAST(p.node_id AS TEXT) || ',', CASE WHEN w.visited_path LIKE '%,' || CAST(p.node_id AS TEXT) || ',%' THEN 1 ELSE 0 END FROM walk w INNER JOIN hierarchy_nodes p ON p.node_id = w.parent_id WHERE w.is_cycle = 0 AND w.depth < 20) SELECT origin_id, node_id AS repeated_node_id, node_name AS repeated_node_name, depth, visited_path FROM walk WHERE is_cycle = 1 ORDER BY origin_id;Why this works
Each node starts an independent upward walk. Delimiters prevent partial-ID matches, the cycle flag preserves the first repeated node for diagnosis, and the recursive WHERE clause stops expansion immediately after detection. The isolated fixture includes a valid tree, an orphan, and a disconnected cycle so a root-only or unguarded solution cannot pass accidentally.
Success check
The three cyclic origins are detected once each; valid, orphaned, and acyclic nodes are not flagged.
Expected result
Use this output to verify values, aliases, ordering, and row count.
| origin_id | repeated_node_id | repeated_node_name | depth | visited_path |
|---|---|---|---|---|
| 90 | 90 | Cycle A | 3 | ,90,91,92,90, |
| 91 | 91 | Cycle B | 3 | ,91,92,90,91, |
| 92 | 92 | Cycle C | 3 | ,92,90,91,92, |
Learn the concepts behind this answer
Strengthen your understanding with these targeted learning topics:
Continue practicing
Build the next SQL skill
SQL Joins
Practice reliable INNER, LEFT, FULL, CROSS, self, semi, anti, range, temporal, and many-to-many join patterns.
CTEs & Window Functions
Practice modular CTE pipelines, deterministic window analytics, period comparisons, deduplication, frames, and gaps-and-islands.
SQL Subqueries
Practice scalar, derived-table, correlated, EXISTS, NULL-safe anti-subquery, quantified, and row-subquery patterns.
Open the interactive workspace and practice across SQL topics.