select id, 'Leaf' as node
from tree
where id NOT IN ( select distinct t1.id as node
                 from tree t1 join tree t2 on t1.id = t2.p_id )
union
select distinct p_id, 'Inner' as node
from tree
where p_id NOT IN( select id from tree where p_id IS NULL)
union
select id, 'Root'
from tree
where p_id is NULL
order by id

id    p_id
-----------
1   2
3   2
6   8
9   8
2   5
8   5
5   (null)

1   Leaf
2   Inner
3   Leaf
5   Root
6   Leaf
8   Inner
9   Leaf