I have a tree structure of light bulbs. I want to turn on all the light bulbs starting from the leafs of the tree. A light bulb cannot be turned on unless all its immediate children are turned on.

The relation between the nodes in the tree structure is represented by table A:

Table A:

node_id integer
child_node_id integer

Table B represents the nodes in the tree:

Table B:

id integer
state boolean

The state of table B represents the states true = on and false = off.

I would like to select all the light bulbs which are turned off AND has all immediate children turned on.

This is probably very simple, but I can't seem to get my head around it.

  • Select nodes with all immediate children turned on or all children recursively? – Erwin Brandstetter May 28 '13 at 10:28
  • Ahh... yes thats a detail which is missing - thanks! – Chau May 28 '13 at 10:30
  • Including or excluding nodes without children? – Erwin Brandstetter May 28 '13 at 10:33

I would first rethink the design. You only need one table:

  id integer PRIMARY KEY
 ,parent_id integer REFERENCES c(id)
 ,state boolean

With the layout as presented in the question, the query could be:

FROM   a
JOIN   b ON a.node_id = b.id
LEFT   JOIN a ca ON ca.child_node_id = a.node_id
LEFT   JOIN b cb ON cb.id = ca.node_id AND cb.state = FALSE
WHERE  b.state = FALSE
AND    cb.id IS NULL

This includes nodes that are turned off and have no children at all.
To exclude nodes without children, replace the first LEFT JOIN with a plain JOIN.

Or, may be faster:

FROM   a
JOIN   b ON a.node_id = b.id
   SELECT 1 
   FROM   a ca
   JOIN   b cb ON cb.id = ca.node_id
   WHERE  ca.child_node_id = a.node_id
   AND    cb.state = FALSE
  • My example is simplified and I need the structure for other reasons. – Chau May 28 '13 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.