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