Finding the root node of a descendant in an Adjacency List

Question

In an Adjacency List table, given the id of a node, how can I find it's associated root node?

Note:

The table contains multiple trees so I cannot simply search for the null parentId.

Further Information:

This is what I currently have, any issues or improvements to this?

with tree as
(
    select 
        t.*

    from table1 t
    where t.id = @id

    union all 

    select 
        t2.*

    from tree
    join table1 t2 on tree.parentId = t2.id
) 

select * 
from tree
where parentId is null

score 2 · Accepted Answer · answered Aug 28 '13 at 08:00

I don't think any of the solutions offered were better than my own so I ended up going with this:

with tree as
(
    select 
        t.*

    from table1 t
    where t.id = @id

    union all 

    select 
        t2.*

    from tree
    join table1 t2 on tree.parentId = t2.id
) 

select * 
from tree
where parentId is null

score 0 · Answer 2 · answered Jul 27 '12 at 12:47

Here is code with WHILE loop. Works with multiple trees in the table:

declare @current_node int
declare @parent_node int
declare @MAX_ITERATIONS int
declare @count int

SET @current_node=@id -- node to start with
SET @MAX_ITERATIONS = 100 --maximum iterations count
SET @count=0 


while(@count<@MAX_ITERATIONS) -- to prevent endless loop  
begin
 select @parent_node=parentid from tree where id=@current_node
 if @parent_node is null -- root is found
  begin 
    break; 
  end
 set @current_node=@parent_node 
 SET @count=@count+1
end

if (@count=@MAX_ITERATIONS) SET @current_node=NULL --if it was endless loop

select @current_node; -- output root id

score 0 · Answer 3 · edited May 23 '17 at 12:19

0

This solution has worked well for me. Can't for sure say if the performance is faster than yours though.

declare @base_id as int;
set @base_id = 1;
WITH n(id) AS 
   (SELECT id 
    FROM table
    WHERE id = @base_id
        UNION ALL
    SELECT nplus1.ID
    FROM table as nplus1, n
    WHERE n.id = nplus1.ParentID)
SELECT id FROM n

(Answer Modified from Simulation of CONNECT BY PRIOR of ORACLE in SQL SERVER)

edited May 23 '17 at 12:19

Community

1
1

answered Nov 08 '12 at 18:32

NSjonas

10,693
9
66
92

Thanks for this. However i'm not sure it answers the question. Unless i'm doing something wrong it seems to return the id's of each node in the subtree. – Brett Postin Nov 13 '12 at 17:03
oh yea sorry. I misread the question... when i get some free time ill see if i can rework my answer – NSjonas Nov 14 '12 at 17:59

Finding the root node of a descendant in an Adjacency List

3 Answers3