SQL Server CTE for Recursion and Ordering

Question

I have the following table in SQL Server (2012):

MyTable:

Id      __ParentId      Priority
1       NULL            NULL    
2       1               100     
3       1               300     
4       1               200     
5       4               100     
6       4               200     
7       6               100     
8       5               100     
9       5               200     
10      9               100     
11      5               50      

The __ParentId column references the Id to know the parent of any one row and it can go down to many levels of recursion (for example, Id 8 is a child of 5 which is a child of 4 which is a child of 1).

Also, there is a Priority column showing the order the children should appear within a parent (lowest number getting precedence).

So, the final table I'd like to get is:

Id      __ParentId  Priority    Order   
1       NULL        NULL        1       
2       1           100         2       
4       1           200         3       
5       4           100         4       
11      5           50          5       
8       5           100         6       
9       5           200         7       
10      9           100         8       
6       4           200         9       
7       6           100         10      
3       1           300         11      

To explain a touch, we have that 2 is a child of 1 and has the highest priority, but has no children, so we stop there, then 4 is the next priority child, so it goes next, but then we diverge into its children and their children based upon priority and hierarchy.

Or, to explain via a tree structure:

 1
    2
    4
        5
            11
            8
            9
                10
        6
            7
    3

I can create the CTE that will give me the children of a parent, but I can't figure out a good way to get the correct ordering, so can't even provide a good SQL I've been trying.

Answer 1

SQL2008+:

Try following solution:

DECLARE @TableA TABLE (
    Id          INT NOT NULL PRIMARY KEY,
    __ParentId  INT NULL,
    [Priority]  INT NULL
);

INSERT @TableA (Id, __ParentId, [Priority])
VALUES 
(1 ,NULL,NULL),   
(2 ,1   ,100 ),   
(3 ,1   ,300 ),   
(4 ,1   ,200 ),   
(5 ,4   ,100 ),   
(6 ,4   ,200 ),   
(7 ,6   ,100 ),   
(8 ,5   ,100 ),   
(9 ,5   ,200 ),   
(10,9   ,100 ),   
(11,5   ,50  );

WITH CteRecursive
AS (
    SELECT  a.Id, a.__ParentId, a.[Priority], CONVERT(HIERARCHYID, '/' + LTRIM(a.Id) + '/') AS HID
    FROM    @TableA a
    WHERE   a.__ParentId IS NULL
    UNION ALL 
    SELECT  cld.Id, cld.__ParentId, cld.[Priority], CONVERT(HIERARCHYID, prt.HID.ToString() + LTRIM(cld.[Priority]) + '/') AS HID
    FROM     CteRecursive prt -- Parent
    JOIN @TableA cld ON prt.Id = cld.__ParentId -- Child
    WHERE   cld.__ParentId IS NOT NULL
)
SELECT *, r.HID.ToString() AS HIDToString FROM CteRecursive r
ORDER BY r.HID ASC

Results:

Demo

Note #1: This solution uses one property of HIERARCHYID ordering: HID values are ordered using depth first approach (this means parent and then all children).

Given two hierarchyid values a and b, a less than b means a comes before b in a depth-first traversal of the tree. Indexes on hierarchyid data types are in depth-first order, and nodes close to each other in a depth-first traversal are stored near each other. For example, the children of a record are stored adjacent to that record. For more information, see Hierarchical Data (SQL Server).

Reference

Answer 2

This is a standard recursive cte, but with a little twist. We add a SEQUENCE which is a compound string of row_numbers order by (in this case) Priority.

Example

Declare @YourTable Table ([Id] varchar(50),[__ParentId] varchar(50),[Priority] varchar(50))
Insert Into @YourTable Values
 (1,NULL,NULL)
,(2,1,100)
,(3,1,300)
,(4,1,200)
,(5,4,100)
,(6,4,200)
,(7,6,100)
,(8,5,100)
,(9,5,200)
,(10,9,100)
,(11,5,50)

Declare @Top    int         = null      --<<  Sets top of Hier Try 4
Declare @Nest   varchar(25) = '|-----'  --<<  Optional: Added for readability

;with cteP as (
      Select Seq  = cast(10000+Row_Number() over (Order by [Priority]) as varchar(500))
            ,ID
            ,__ParentId 
            ,Lvl=1
            ,Priority
      From   @YourTable 
      Where  IsNull(@Top,-1) = case when @Top is null then isnull(__ParentId ,-1) else ID end
      Union  All
      Select Seq  = cast(concat(p.Seq,'.',10000+Row_Number() over (Order by r.[Priority])) as varchar(500))
            ,r.ID
            ,r.__ParentId 
            ,p.Lvl+1
            ,r.Priority
      From   @YourTable r
      Join   cteP p on r.__ParentId  = p.ID)
Select A.ID
      ,A.__ParentId 
      ,A.Lvl
      ,A.Priority
      ,Name = Replicate(@Nest,A.Lvl-1) +cast(ID as varchar(25))
 From cteP A
 Order By Seq

Returns