Find leaf nodes in hierarchical tree

Question

I have a table in my database which stores a tree structure. Here are the relevant fields:

mytree (id, parentid, otherfields...)

I want to find all the leaf nodes (that is, any record whose id is not another record's parentid)

I've tried this:

SELECT * FROM mytree WHERE `id` NOT IN (SELECT DISTINCT `parentid` FROM `mytree`)

But that returned an empty set. Strangely, removing the "NOT" returns the set of all the non-leaf nodes.

Can anyone see where I'm going wrong?

Update: Thanks for the answers guys, they all have been correct and worked for me. I've accepted Daniel's since it also explains why my query didn't work (the NULL thing).

Answer 1

No clue why your query didn't work. Here's the identical thing in left outer join syntax - try it this way?

select a.*
from mytree a left outer join
     mytree b on a.id = b.parentid
where b.parentid is null

Answer 2

Your query didn't work because the sub-query includes NULL. The following slight modification works for me:

SELECT * FROM `mytree` WHERE `id` NOT IN (
    SELECT DISTINCT `parentid` FROM `mytree` WHERE `parentid` IS NOT NULL)

Answer 3

SELECT * FROM mytree AS t1
LEFT JOIN mytree AS t2 ON t1.id=t2.parentid
WHERE t2.parentid IS NULL

Answer 4

Select * from mytree where id not in (Select distinct parentid from mytree where parentid is not null)

http://archives.postgresql.org/pgsql-sql/2005-10/msg00228.php