Postgres 11

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.

select version();


version


PostgreSQL 11.4 (Debian 11.4-1.pgdg90+1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 6.3.0-18+deb9u1) 6.3.0 20170516, 64-bit


CREATE TABLE tree (parent VARCHAR(10), child VARCHAR(10));
INSERT INTO tree VALUES ('a','b'), ('a','c'), ('b','e'), ('b','f'), ('a','d'), ('b','g'),
('c','h'), ('c','i'), ('d','j'), ('f','k'), ('x','y'), ('y','z'), ('m','n');
13 rows affected

WITH rcte (child, parent) AS
(
  SELECT parent AS child, NULL AS parent FROM tree t1 
    WHERE Parent NOT IN (SELECT child FROM tree)
  UNION ALL

  SELECT t2.child, t3.parent FROM tree t2
  JOIN tree t3 ON t2.parent >= t3.parent
  -- ORDER BY child
)
SELECT DISTINCT parent, child FROM rcte
ORDER BY parent NULLS FIRST, child;


parent
child


null
a

null
m

null
x

a
b

a
c

a
d

a
e

a
f

a
g

a
h

a
i

a
j

a
k

a
n

a
y

a
z

b
e

b
f

b
g

b
h

b
i

b
j

b
k

b
n

b
y

b
z

c
h

c
i

c
j

c
k

c
n

c
y

c
z

d
j

d
k

d
n

d
y

d
z

f
k

f
n

f
y

f
z

m
n

m
y

m
z

x
y

x
z

y
z

parent	child
null	a
null	m
null	x
a	b
a	c
a	d
a	e
a	f
a	g
a	h
a	i
a	j
a	k
a	n
a	y
a	z
b	e
b	f
b	g
b	h
b	i
b	j
b	k
b	n
b	y
b	z
c	h
c	i
c	j
c	k
c	n
c	y
c	z
d	j
d	k
d	n
d	y
d	z
f	k
f	n
f	y
f	z
m	n
m	y
m	z
x	y
x	z
y	z