Preorder tree traversal using recursive CTEs in SQL

Question

I need to traverse a node tree in pre order to generate a menu listing and so far I've come up with this recursive CTE:

    WITH RECURSIVE nodes AS (
    SELECT '' as spacer,
           1::numeric as level,
           (rank() OVER (PARTITION BY parent_id order by name ASC ))::numeric as node_rank,
           node_tree.*
    FROM node_tree
    where parent_id IS NULL
UNION
    SELECT parent.spacer || '-' as spacer,
           parent.level * 10.0 as level,
           parent.node_rank + (rank()  OVER (PARTITION BY node.parent_id order by node.name ASC )) / (parent.level * 10.0) as node_rank,
           node.*
    FROM node_tree node
             join nodes parent
                  on parent.id = node.parent_id
)
SELECT 
  trim(spacer || ' ' || name) as item_name,
  id,
  parent_id,
  name
FROM nodes
order by node_rank nulls first, name

Assuming that I need to keep the self referencing structure of the table, is there any better method?

This is the minimal schema and sample data:

CREATE TABLE node_tree (
  id uuid primary key,
  parent_id uuid default null,
  name text
  );
  
ALTER TABLE node_tree ADD CONSTRAINT node_parent_check
CHECK (parent_id is NULL OR parent_id <> id);

ALTER TABLE node_tree 
    ADD CONSTRAINT node_parent_fk 
    FOREIGN KEY (parent_id)
    REFERENCES node_tree(id);
    
    
INSERT INTO node_tree (id,parent_id,name) VALUES
('B4352249-3BCC-4110-964B-368AAA2DCE4C', null, 'Node 1'),
('AE3C21B1-9F4E-4C62-A2C7-2C729591CE60', 'B4352249-3BCC-4110-964B-368AAA2DCE4C', 'Node 1.1'),
('CED81F20-6598-42EA-95F8-2D5E8B1FCA73', 'AE3C21B1-9F4E-4C62-A2C7-2C729591CE60', 'Node 1.1.1'),
('9B2BC4D7-D387-4726-A3E2-2466883152CC', 'AE3C21B1-9F4E-4C62-A2C7-2C729591CE60', 'Node 1.1.2'),
('1492A9D9-D24F-47E6-9926-9D198B7F57A0', 'B4352249-3BCC-4110-964B-368AAA2DCE4C', 'Node 1.2'),
('F1B22F5B-34A7-4A92-9792-C2D023147E4D', '1492A9D9-D24F-47E6-9926-9D198B7F57A0', 'Node 1.2.1'),
('5B0AA9B2-1DB8-4DDE-A184-77872F2BC990', '1492A9D9-D24F-47E6-9926-9D198B7F57A0', 'Node 1.2.2'),
('7450E2EC-3E20-45F0-BE59-9F5BEE7D2955', null, 'Node 2'),
('F60B7772-D6E3-42A7-8AAE-D6CB862F4D96', '7450E2EC-3E20-45F0-BE59-9F5BEE7D2955', 'Node 2.1'),
('954C6010-DA37-41B1-8933-93B15552E6CB', 'F60B7772-D6E3-42A7-8AAE-D6CB862F4D96', 'Node 2.1.1'),
('2F3EBEC7-B038-4E7D-B7AF-F22D524B1AF8', '954C6010-DA37-41B1-8933-93B15552E6CB', 'Node 2.1.1.1'),
('4BA13434-2DA5-4913-B9F6-5AFEF4892000', '954C6010-DA37-41B1-8933-93B15552E6CB', 'Node 2.1.1.2'),
('337238CC-FED0-40D2-B54B-603A36C075A0', 'F60B7772-D6E3-42A7-8AAE-D6CB862F4D96', 'Node 2.1.2'),
('F7996999-D024-428A-BF61-78958695DDB3', null, 'Node 3'),
('81BAE0B8-70CF-4152-BCBF-632964E30904', 'F7996999-D024-428A-BF61-78958695DDB3', 'Node 3.1'),
('E88F9BD9-4288-46FC-9972-215623BE3949', '81BAE0B8-70CF-4152-BCBF-632964E30904', 'Node 3.1.1'),
('992AE037-9DAA-49D9-A725-AC1BBCE46037', null, 'Node 4'),
('9CFC7634-E1DA-4AC3-9D9D-4995B28EB148', '992AE037-9DAA-49D9-A725-AC1BBCE46037', 'Node 4.1'),
('E53C022B-1E4E-4D6F-A740-26A23211BF1F', '9CFC7634-E1DA-4AC3-9D9D-4995B28EB148', 'Node 4.1.1');

Here is a DB fiddle of it: DB Fiddle

Is the tree always a binary tree? Should we consider that the lowest id is on the left and the highest on the right? — Fabian Pijcke
– Fabian Pijcke, Commented Dec 11, 2020 at 8:27
Your third column could be used (somewhat adjusted) to use the ltree extension: postgresql.org/docs/current/ltree.html This is a plugin which can handle tree structures stored like "1.2.3" very well. So, you don't need to created huge recursive CTEs, further reading: patshaughnessy.net/2017/12/13/… — S-Man
– S-Man, Commented Dec 11, 2020 at 8:29
@FabianPijcke The tree is not a binary one, each node can have an indefinite number of descendants. — Alessandro Morelli
– Alessandro Morelli, Commented Dec 11, 2020 at 10:32
@S-Man The name in the third column is just an example to help myself compose a sample tree. In reality, the names of the nodes are descriptive names used in an UI element and cannot be constrained to a specific format. — Alessandro Morelli
– Alessandro Morelli, Commented Dec 11, 2020 at 10:34

Ciro Santilli OurBigBook.com · Accepted Answer · 2023-10-12 16:22:32Z

Path enumeration with arrays

This will use up a lot of "unnecessary" memory for deeply nested trees, but it is the best I can come up with and should work in some use cases at least.

Table:

psql <<'EOF'
DROP TABLE  IF EXISTS "tmp";
CREATE TABLE "tmp" (
  "id" INTEGER PRIMARY KEY,
  "parentId" INTEGER,
  "childIndex" INTEGER NOT NULL,
  "value" INTEGER NOT NULL,
  "name" TEXT NOT NULL,
  FOREIGN KEY ("parentId") REFERENCES "tmp"("id")
);
EOF

Data:

psql <<'EOF'
INSERT INTO "tmp" VALUES
(3, NULL, 0, 1, 'one'  ),
(1, 3,    0, 2, 'two'  ),
(2, 3,    1, 3, 'three'),
(0, 1,    0, 4, 'four' ),
(4, 1,    1, 5, 'five' )
EOF

Represented tree:

Query:

psql <<'EOF'
WITH RECURSIVE "cte" (
  "id",
  "parentId",
  "childIndex",
  "value",
  "name",
  "prefix"
) AS (
  SELECT
    "id",
    "parentId",
    "childIndex",
    "value",
    "name",
    array[0]
  FROM "tmp"
  WHERE "parentId" IS NULL

  UNION ALL

  SELECT
    "child"."id",
    "child"."parentId",
    "child"."childIndex",
    "child"."value",
    "child"."name",
    "parent"."prefix" || "child"."childIndex"
  FROM "tmp" AS "child"
  JOIN "cte" AS "parent"
    ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "cte"
ORDER BY "prefix"
EOF

Output in the desired preorder:

 id | parentId | childIndex | value | name  | prefix  
----+----------+------------+-------+-------+---------
  3 |          |          0 |     1 | one   | {0}
  1 |        3 |          0 |     2 | two   | {0,0}
  0 |        1 |          0 |     4 | four  | {0,0,0}
  4 |        1 |          1 |     5 | five  | {0,0,1}
  2 |        3 |          1 |     3 | three | {0,1}

SEARCH is a shortcut keyword that produces the exact same query with less verbose code:

psql <<'EOF'
WITH RECURSIVE "cte" (
  "id",
  "parentId",
  "childIndex",
  "value",
  "name"
) AS (
  SELECT
    "id",
    "parentId",
    "childIndex",
    "value",
    "name"
  FROM "tmp"
  WHERE "parentId" IS NULL

  UNION ALL

  SELECT
    "child"."id",
    "child"."parentId",
    "child"."childIndex",
    "child"."value",
    "child"."name"
  FROM "tmp" AS "child"
  JOIN "cte" AS "parent"
    ON "child"."parentId" = "parent"."id"
)
SEARCH DEPTH FIRST BY "childIndex" SET "prefix"
SELECT * FROM "cte"
ORDER BY "prefix"
EOF

The trick is to create a prefix array column that registers the full path to each element, and then order by that, which happens in lexicographical order.

This and some other related techniques are also documented in the manual at: https://www.postgresql.org/docs/16/queries-with.html#QUERIES-WITH-RECURSIVE

Tested on Postgresql 15.4, Ubuntu 23.04.

Related: https://dba.stackexchange.com/questions/63153/how-do-i-sort-the-results-of-a-recursive-query-in-an-expanded-tree-like-fashion

Collectives™ on Stack Overflow

Preorder tree traversal using recursive CTEs in SQL

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related