Recursive CTEs for trees and graphs

WITH RECURSIVE lets a CTE refer to itself. It has two parts joined by UNION ALL (or UNION):

WITH RECURSIVE name AS (
  anchor query          -- runs once
  UNION ALL
  recursive query       -- refers to name
)

Despite the name, it is a loop, not recursion. PostgreSQL runs the anchor and puts its rows in a working table. Then it repeats: run the recursive term with name meaning only the rows produced by the previous step, append the new rows to the result, make them the new working table. It stops when a step produces no rows.

Walking a hierarchy

The anchor selects the root (the employee with no manager). Each step joins employees to the rows found in the step before, one level deeper. Carrying depth + 1 and a growing path along gives every row its position in the tree.

1CREATE TABLE employees (id int PRIMARY KEY, name text NOT NULL, manager_id int REFERENCES employees (id));2INSERT INTO employees VALUES3  (1, 'Tamar', NULL), (2, 'Giorgi', 1), (3, 'Nino', 1), (4, 'Ana', 2), (5, 'Luka', 4);

1WITH RECURSIVE chain AS (2  SELECT id, name, 0 AS depth, name AS path3  FROM employees4  WHERE manager_id IS NULL5  UNION ALL6  SELECT e.id, e.name, c.depth + 1, c.path || ' > ' || e.name7  FROM employees e8  JOIN chain c ON e.manager_id = c.id9)10SELECT id, depth, path11FROM chain12ORDER BY path;

Ordering by the path string prints the tree depth-first, each manager followed by their reports. (That works for these names; for a tree whose names could contain the separator, build an array path instead.)

Ancestors and descendants

Many tree questions ("how many people report to X, directly or not?") need every (ancestor, descendant) pair. Start from the direct edges, then extend each pair one level down:

WITH RECURSIVE pairs AS (
  SELECT manager_id AS ancestor, id AS descendant
  FROM employees WHERE manager_id IS NOT NULL
  UNION ALL
  SELECT p.ancestor, e.id
  FROM pairs p JOIN employees e ON e.manager_id = p.descendant
)
SELECT ancestor, count(*) FROM pairs GROUP BY ancestor;

Cycles: UNION versus UNION ALL versus CYCLE

A tree always ends; a graph with a cycle never does under UNION ALL, because each step keeps finding the same nodes again. Two remedies:

• UNION instead of UNION ALL discards rows already in the result, so the loop ends once nothing new turns up. This works only when the rows carry nothing that keeps changing: add a hops counter and every row is new again.
• The CYCLE clause (PostgreSQL 14+) tracks the path for you and marks a row whose node was already visited on that path; that row is kept, flagged, and not expanded further.

1CREATE TABLE links (src int NOT NULL, dst int NOT NULL);2INSERT INTO links VALUES (1, 2), (2, 3), (3, 1), (3, 4);

1WITH RECURSIVE walk (node, hops) AS (2  SELECT 1, 03  UNION ALL4  SELECT l.dst, w.hops + 15  FROM links l6  JOIN walk w ON l.src = w.node7) CYCLE node SET is_cycle USING route8SELECT node, hops, is_cycle, route::text AS route9FROM walk10ORDER BY hops, node;

1CREATE TABLE links (src int NOT NULL, dst int NOT NULL);2INSERT INTO links VALUES (1, 2), (2, 3), (3, 1), (3, 4);

1WITH RECURSIVE reach (node) AS (2  SELECT 13  UNION4  SELECT l.dst5  FROM links l6  JOIN reach r ON l.src = r.node7)8SELECT string_agg(node::text, ',' ORDER BY node) AS reachable_from_19FROM reach;

Common mistakes

• Forgetting that the recursive term sees only the previous step's rows, and writing a condition that assumes it sees the whole result.
• Using UNION ALL on data that can contain a cycle and hitting the statement timeout instead of an answer.
• Counting only direct reports when the question says "directly or indirectly".
• Expecting UNION to stop a cycle while each row also carries a growing counter or path, which makes every row distinct.

What interviewers ask

• How does a recursive CTE execute? Anchor once, then repeat the recursive term over the previous step's rows until a step returns none.
• How do you stop it looping on cyclic data? UNION for plain node sets, a visited-path array, or the CYCLE clause; also a depth limit as a safety net.
• Find all managers above an employee. Anchor on the employee, join upwards on id = manager_id each step.