sql - Postgres で再帰 CTE を使用して AST をビルドする

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 を計算する方法: AND(NOT(AND(K, OR(X, A, B))), OR(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を持っています）