Home > Software engineering >  Get all of the low-level children of a node
Get all of the low-level children of a node

Time:11-29

I am struggling with the writing of a query for PostgreSQL. The table resembles a tree and every item can have n children. I would like to get only and all the children of the lowest level(s) (which don't have any children by themselves) of a given element of the tree.

The structure:

CREATE TABLE items
(
    ikey integer NOT NULL,
    description character varying(255),
    parent integer,
    CONSTRAINT i_pk PRIMARY KEY (ikey),
    CONSTRAINT i_relation FOREIGN KEY (parent)
        REFERENCES items (ikey) MATCH SIMPLE
)

Some values of the table would look like this:

 1  "Products"  NULL --Parent
 2  "Metal" 1
 3  "Nails" 2
 4  "Chains"    2
 5  "Bicycle Chains"    4
 6  "Shimano Bicycle Chains"    5
 7  "Shimano Bicycle Chains"    5
 8  "7mm chain, black"    4
 9  "Wood"  1
 10 "Cutting Boards"    8
 11 "Cutting Board Holder" 8

Most of the solutions on SO deal with not very deep trees which have just 1-2 levels. Or it is known from which parent the children are required.

I would like to select all children of "Chains" (4), which would give the following result:

6   "Shimano Bicycle Chains"    5
7   "Shimano Bicycle Chains"    5
8   "7mm chain, black"    4

To be honest, recursive queries are not my strongest skill. I had the idea already to search upside down - getting all items first which are never used as parents and then going down, but this only shifts the problem to the point again that I have to go down recursively from the given parent which seems a bit over the top.

CodePudding user response:

If you want to find all children items of an item in all levels you can write a recursive CTE. For example:

with recursive
n as (
  select * from items where parent = 4 -- Children of "Chains"
 union all
  select i.*
  from n
  join items i on i.parent = n.ikey
)
select * from n

Result:

 ikey  description               parent 
 ----- ------------------------- ------ 
 5     Bicycle Chains            4      
 8     7mm Chain Black           4      
 6     Shimano Bicycle Chains 1  5      
 7     Shimano Bicycle Chains 2  5      

See running example at DB Fiddle.

CodePudding user response:

You do not need a recursive query. Instead, you can simply select the rows with ikeys that do not occur as parents:

select i1.* from items i join items i1 on i.ikey = i1.parent where i.parent = 4 and 
    not exists (select 1 from items i2 where i2.parent = i1.ikey)

CodePudding user response:

Another recursive CTE, with extras.
The base key that started the recursion & level of the tree.

WITH RECURSIVE RCTE_OFFSPRING AS (
  SELECT ikey as base, 0 as lvl
  , ikey, description, parent
  FROM items
  WHERE ikey = 4
  
  UNION ALL
  
  SELECT cte.base, cte.lvl   1
  , itm.ikey, itm.description, itm.parent
  FROM items itm
  JOIN RCTE_OFFSPRING cte 
    ON cte.ikey = itm.parent
)
SELECT * 
FROM RCTE_OFFSPRING
WHERE lvl > 0
ORDER BY base, lvl, ikey
base lvl ikey description parent
4 1 5 Bicycle Chains 4
4 1 8 7mm chain, black 4
4 2 6 Shimano Bicycle Chains 5
4 2 7 Shimano Bicycle Chains 5

db<>fiddle here

  • Related