Find the respective top-level element for each bottom element in a hierarchical table

Question

I am trying to query a table that represents hierarchical data to find the top-level element for each bottom element. Here, an example:

ID    PARENTID               
----- --------  
1     1
2     1
3     2
4     2
5     3
6     6
7     6
8     6
9     4
10    10

I want to have a query that returns the ID of the lowest elements in the hierarchy along with the ultimate Parent for that ID. So, the result should look like this:

ID    UltimateParentID               
----- ----------------  
5     1
7     6
8     6
9     1
10    10

Is there a way to get this result with a recursive SQL query?

So far, I couldn't find any SQL code that fits my needs.

Answer 1

with rec(root, id, parentid, lvl) as (
  select id, id, parentid, 1 from t 
  where not exists (select 1 from t x where parentid = t.id and parentid <> id)
  union all
  select rec.root, t.id, t.parentid, rec.lvl + 1 
  from rec join t on rec.parentid = t.id and t.id <> t.parentid)
select root, parentid 
from (
  select root, parentid, lvl, max(lvl) over (partition by root) mxl from rec) r
where lvl = mxl 

Demo for: SQL Server and for Oracle

It is almost classic recursive query except facts that you have rows like (6, 6) and (10, 10) causing cycles, so we have to eliminate them in processing. Last part with analytic max() is used to find leaf (ultimate) rows,