views:

31

answers:

1

Given the following table:

create table TreeNode
(
  ID int not null primary key,
  ParentID int null foreign key references TreeNode (ID)
)

How could I write a common table expression to start at the root (WHERE ParentID IS NULL) and traverse its descendants until the result set contains some target node (e.g., WHERE ID = n)? It's easy to start at the target node and traverse upward to the root, but that wouldn't generate the same result set. Specifically, nodes having the same parent as the target node wouldn't be included.

My first attempt was:

with Tree as
(
  select
    ID,
    ParentID
  from
    TreeNode
  where
    ParentID is null
  union all select
    a.ID,
    a.ParentID
  from
    TreeNode a
    inner join Tree b
      on b.ID = a.ParentID
  where
    not exists (select * from Tree where ID = @TargetID)
)

Which gives the error: Recursive member of a common table expression 'Tree' has multiple recursive references.

NOTE: I'm only interested in top-down traversal.

+1  A: 

UPDATE 2:

A third attempt that "traverses" the tree in both directions.

Build a CTE of all ParentIDs from Target to root. Then, select from tree the nodes whose ID or Parent shows up in the short list.

--
;
WITH    Tree
          AS ( SELECT   ID
                       ,ParentID
               FROM     TreeNode
               WHERE    [ID] = @targetId
               UNION ALL
               SELECT   a.ID
                       ,a.ParentID
               FROM     TreeNode a
                        INNER JOIN Tree b ON b.ParentID = a.ID
             )
    SELECT  *
    FROM    [dbo].[TreeNode] n
    WHERE  EXISTS (SELECT *
                   FROM [Tree] t
                   WHERE [t].[ID] = [n].[ID]
                         OR [t].[ID] = [n].[ParentID]
                  )
Brad
I don't think we can assume that nodes higher in the tree always have lower IDs.
Daniel
@Daniel, so noted. I've updated my query. It still works in my small sample set.
Brad
The question is specifically how to traverse top-down. I mention a problem with bottom-up in the OP.
Daniel
@Daniel, very true. I missed that. I have given another trial of down-traversal. It begins with **UP-traversal**, but then goes back and gets all the nodes that belong along the way.
Brad
Shouldn't that last line be: `[t].[ParentID] = [n].[ID]`?
Daniel
@Daniel, if you make the last line `[t].[ParentID] = [n].[ID]` you will only be pulling back the nodes where `[t].[ID] = [n].[ID]` (at least it is so in my test).
Brad
Ah, you're right. Sorry. I had the aliases reversed in my mind.
Daniel