Tree traversal using WITH RECURSIVE queries in Postgres

Posted on 13-01-2015 09:56 by graham
This tutorial describes how you can traverse a tree structure using Postgres queries.

Let's imagine we have a simple tree structure in form of a Postgres relation:
CREATE TABLE items
(
id serial NOT NULL,
name character varying(30) NOT NULL,
parentid integer,
CONSTRAINT items_pkey PRIMARY KEY (id),
CONSTRAINT item_fkey FOREIGN KEY (parentid)
REFERENCES items (id) MATCH SIMPLE
ON UPDATE NO ACTION ON DELETE NO ACTION
)


What we want to do is to find all direct and indirect children of a given node. This can be easily achieved using Postgres WITH RECURSIVE query:
WITH RECURSIVE subitems (id, name, parentid, path, depth) AS (
SELECT id, name, parentid, ARRAY[parentid], 1 FROM items WHERE parentid is null
UNION ALL
SELECT i.id, i.name, i.parentid, i.parentId || path, si.depth + 1
FROM subitems si, items i
WHERE si.id = i.parentid
)

-- select all subnodes of node with name = 'C'
SELECT *
FROM subitems
where path[1] = 1


If you want the path column to be a concatenation of text values, you need to cast it explicitly to the character varying() type:
WITH RECURSIVE subitems (id, name, parentid, path, depth) AS (
SELECT id, name, parentid, ARRAY[name], 1 FROM items WHERE parentid is null
UNION ALL
SELECT i.id, i.name, i.parentid, array_append(path, i.name)::character varying(30)[], si.depth + 1
FROM subitems si, items i
WHERE si.id = i.parentid
)

-- select all subnodes of node with ID = 1
SELECT *
FROM subitems
where path[1] = 'C'
Comments

 

Add comment

Has this tutorial been helpful to you? Or do you see anything wrong? We appreciate your opinion!
Your comment:
Show formatting hints
HTML is disallowed, but in your text you can use the following markup
  • [code][/code] for a block of code
  • [tt][/tt] for inline code
  • [link]link href|link anchor[/link] for links
  • [b][/b] for bold text
Email:
+ Ask a question
If you have a technical question related to programming and computers, ask it here. Other users will help you solve it!
Unanswered questions
Share your knowledge by helping others solve their problems