Finding the root node of a descendant in an Adjacency List
-
23-06-2021 - |
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
Solution
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
OTHER TIPS
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
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)
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow