Построить AST с рекурсивным CTE в Postgres

Question

Учитывая следующую таблицу:

create table tree
(
    id int,
    parent_id int REFERENCES tree(id),
    operator varchar,
    primary key(id)
);

insert into tree values
(1, null, 'AND'),
(2, 1, 'NOT'),
(3, 1, 'OR'),
(4, 2, 'AND'),
(5, 3, 'Y'),
(6, 3, 'Z'),
(7, 4, 'K'),
(8, 4, 'OR'),
(9, 8, 'X'),
(10, 8, 'A'),
(11, 8, 'B')
;

как я могу вычислить окончательный AST: И (НЕ (И (K, ИЛИ (X, A, B))), ИЛИ (Y, Z))

Я пробовал разные подходы с рекурсивным CTE, но моя проблема в том, что CTE не допускает ни агрегации в рекурсивной части CTE, ни подзапросов, где используется CTE.

Последнее, что я попробовал, было следующее:

with RECURSIVE tree1(id, parent_id, operator, n, cc) as (
    select t.*, 0, cc.cc 
    from tree t, lateral(select count(*) as cc from tree tt where tt.parent_id = t.id) cc 
    where t.parent_id is null
    union ALL
    select t.*, n + 1, cc.cc
    FROM tree t INNER JOIN tree1 a on t.parent_id = a.id, lateral(select count(*) as cc from tree tt where tt.parent_id = t.id) cc
), tree2(id, parent_id, operator, n, cc) AS (
    select t.id, t.parent_id, t.operator, t.n, t.cc
    from tree1 t
    where t.n = (select max(n) from tree1)
    union (
        select p.id, p.parent_id, p.operator || '(' || string_agg(c.operator, ', ') || ')' as operator, p.n, p.cc
        from tree1 p, tree2 c
        where p.id = c.parent_id
        group by p.id, p.parent_id, p.operator, p.n, p.cc
        union
        select p.id, p.parent_id, p.operator, p.n, p.cc
        from tree1 p, tree2 c 
        where p.cc = 0 and p.n + 1 = c.n
    )
)
select * from tree2

, но это не сработало из-за ограничений CTE.

В документах говорится, что CTE завершен по Тьюрингу, но я не могу найти способ вычислить желаемый результат.Я что-то упускаю или мое понимание полноты по Тьюрингу неверно?:)

(у меня Postgres 9.6)