Recursively deleting nodes from a tree in SQL with a single query

demo:db<>fiddle

WITH RECURSIVE dependents AS (                          -- 1.
    SELECT
        dependent,
        array_agg(prereq) as prereqs
    FROM 
        tree
    GROUP BY dependent
), deletions AS (
    SELECT array_cat(ARRAY['A', 'D', 'E', 'I'], array_agg(dependent))             -- 3.
    FROM dependents
    WHERE prereqs <@ ARRAY['A', 'D', 'E', 'I']          -- 2.

    UNION

    SELECT DISTINCT array_cat(del.array_cat, array_agg(dep.dependent) OVER ())
    FROM dependents dep
    JOIN deletions del
    ON NOT(dep.dependent = ANY(del.array_cat)) AND dep.prereqs <@ del.array_cat   -- 4.
)

SELECT * FROM deletions

1. Get all direct prereqs of each dependents
2. Check if there's an array of prereqs that completely fits into your deletion array.
3. aggregate all dependents of these results and the origin array into one as new array for deleted nodes.
4. recursion part: again: check if there are any dependents (new, not already in list) whose prereqs array fits into the expanded deletion nodes and add them into the list.

Although I've shown a solution with one single recursion query. But I am not quiet sure if it performs well on huge and complex data structures.

I would try a second way creating a simple function (sketch):

1. Find all elements that are only leafs with no prereqs. Delete them.
2. Find all dependents with no prereq children. Delete them.
3. Repeat (2) until there's no element with empty prereqs.

Simply put, you can use two CTEs (Common Table Expressions) to identify:

• The "Candidate Nodes": these are all the nodes related to your root nodes, that could potentially be deleted.
• The "Protected Nodes": these are all the nodes that are still at play that are related to other root nodes, and that should not be deleted.

Once you get both sets, the result you want is the Candidates Nodes that are not Protected Nodes. The query could look like:

with recursive cand as ( -- get the candidates nodes
  select distinct prereq as root, prereq as node, null as prereq
    from tree where prereq in ('A', 'D', 'E', 'I')
  union all
  select cand.root, t.dependent, t.prereq
    from cand
    join tree t on t.prereq = cand.node
),
prot as ( -- get the protected nodes
select distinct prereq as root, prereq as node, null as prereq
  from tree
  where prereq not in (select dependent from tree) 
    and prereq not in ('A', 'D', 'E', 'I')
  union all
  select prot.root, t.dependent, t.prereq
    from prot
    join tree t on t.prereq = prot.node
)
select distinct node -- choose candidates that are not protected
  from cand 
  where node not in (select node from prot)
  order by node

Result:

node  
----
A
B
C
D
E
F
G
H
I
J

Now that I see it again, I realize that for the Candidate Nodes you can use the full table instead of a tree. You can simplify the first part of this query, if you wish.

Here's a possibility:

WITH RECURSIVE
    candidate AS (
        -- All edges for initial nodes to delete.
        SELECT
            tree.dependent,
            tree.prereq
        FROM
            tree
        WHERE
            tree.prereq IN ('A', 'D', 'E', 'I')
        UNION ALL
        -- Iteratively add any edges where the prereq is already in
        -- the candidate deletion set.
        SELECT
            tree.dependent,
            tree.prereq
        FROM
            tree
            JOIN candidate ON
                candidate.dependent = tree.prereq
    ),
    survivor AS (
        -- Find all leaf nodes from the candidate set which can
        -- survive because they have at least one prerequisite node
        -- that is *not* in the candidate set.
        SELECT
            candidate1.dependent AS node
        FROM
            candidate AS candidate1
            JOIN tree
                ON candidate1.dependent = tree.dependent
                AND candidate1.prereq != tree.prereq
        WHERE
            NOT EXISTS (
                SELECT 1 FROM
                    candidate AS candidate2
                WHERE
                    candidate2.prereq = tree.prereq
            )
        UNION ALL
        -- Iteratively add any nodes from the candidate set which are
        -- dependent upon a node we've already identified as a
        -- survivor.
        SELECT
            candidate.dependent
        FROM
            candidate
            JOIN survivor ON survivor.node = candidate.prereq
    )
(
    -- The dependent column contains all nodes to delete except the
    -- initial list of nodes to delete (see below).
    SELECT dependent FROM candidate
    EXCEPT
    SELECT node FROM survivor
)
UNION ALL
-- Add in the initial set of nodes to delete.
SELECT * FROM (VALUES ('A'), ('D'), ('E'), ('I')) AS t
ORDER BY 1;

The candidate CTE produces a subset of rows from tree that might be deleted. candidate.dependent becomes the list of candidate nodes to be deleted. survivor is then built by first looking for nodes named in candidate.dependent that have at least one edge to a node that will not be deleted, and then iteratively ("recursively") naming more and more nodes from candidate.dependent that won't be deleted based on survivor nodes previously identified in the CTE.

The odd-looking UNION ALL SELECT ... VALUES ... to include the initial node list in the output of this query is used instead of (SELECT dependent FROM candidate UNION ALL SELECT prereq FROM candidate), the latter of which seemed to be measurably (but maybe not drastically) slower.

EDIT: Here's a simplified version of the above. Unfortunately I think it runs a little slower, but I also think it's a little easier to read.

WITH RECURSIVE
    candidate AS (
        -- All initial nodes to delete.
        SELECT
            *
        FROM
            (VALUES ('A'), ('D'), ('E'), ('I')) AS t (node)
        UNION
        -- Iteratively add any nodes where the prereq is already in
        -- the candidate deletion set.
        SELECT
            tree.dependent
        FROM
            tree
            JOIN candidate ON
                candidate.node = tree.prereq
    ),
    survivor AS (
        -- Find all nodes from the candidate set which can
        -- survive because they have at least one prerequisite node
        -- that is *not* in the candidate set.
        SELECT
            c1.node
        FROM
            candidate AS c1
            JOIN tree
                ON c1.node = tree.dependent
            LEFT JOIN candidate AS c2 ON c2.node = tree.prereq
        WHERE
            c2.node IS NULL
        UNION
        -- Iteratively add any nodes from the candidate set which are
        -- dependent upon a node we've already identified as a
        -- survivor.
        SELECT
            candidate.node
        FROM
            candidate
            JOIN tree ON candidate.node = tree.dependent
            JOIN survivor ON survivor.node = tree.prereq
    )
SELECT node FROM candidate
EXCEPT ALL
SELECT node FROM survivor
ORDER BY 1