Order of Recursion (SQL Server CTE)

Question

I can achieve recursion by using SQL Server's With command (CTE).

WITH MyCTE(ParentID,ID,Name,Level)
AS
(
SELECT ManagerID AS ParentID, UserID AS ID, UserName AS Name, 0 AS Level 
FROM USERS U       
WHERE U.ManagerID IS NULL

UNION ALL

SELECT U.ManagerID AS ParentID, U.UserID AS ID, U.UserName AS Name, H.Level+1 AS Level
FROM USERS U
INNER JOIN MyCTE H ON H.ID = U.ManagerID
)

SELECT ParentID,ID FROM MyCTE

returns

ParentID    ID
NULL        1
1           2
1           3
2           4

What I want to achieve is to reverse this result set. Namely,reversing the root node and the deepest child node as,

ParentID    ID
NULL        4
4           2
2           1
3           1

Couldn't figure out how to programmatically implement this (preferably by using CTE), like by using a parameter to determine the recursion order etc. Any help is greatly appreciated, thanks.

Edit :

Modified this a bit inserting my first CTE's results into a temp table, then using another recursion I reverse the order as (I know "WHERE T.ID = (SELECT MAX(ID) FROM @tmp)" wont work in a real situation, I also gotta determine the deepest node with the "Level" column, just tried to simplify this for this example),

 INSERT INTO @tmp
 SELECT ParentID,ID,Level FROM MyCTE
 WITH MyCTE2(ParentID,ID,Level)
 AS
 (
 SELECT NULL AS ParentID, ID AS ID, 0 AS Level FROM @tmp T 
 WHERE T.ID = (SELECT MAX(ID) FROM @tmp)

 UNION ALL

 SELECT R2.ID AS ParentID, T.ParentID AS ID, R2.Level+1 FROM @tmp T
 INNER JOIN MyCTE2 R2 ON R2.ID = T.ID
 WHERE T.ParentID IS NOT NULL
 )

Original Results (removed the 1,3 pair)

ParentID   ID   Level
  NULL      1     0
    1       2     1
    2       4     2

Reversed results,

ParentID   ID   Level
  NULL      4     0
    4       2     1
    2       1     2

Edit 2:

I did something like this,

SELECT TTT.ParentID,TTT.ID,TTT.Level FROM
(
SELECT ParentID,ID,Level FROM MyCTE2
UNION ALL
SELECT TT.ID AS ParentID,TT.ParentID AS ID,(SELECT Level+1 FROM @tmp WHERE ID=TT.ID) 
AS  Level  FROM
(
SELECT ID FROM @tmp
EXCEPT
SELECT ID FROM MyCTE2
)T INNER JOIN @tmp TT ON TT.ID = T.ID
)TTT
ORDER BY TTT.Level

gives,

ParentID    ID  Level
NULL        4   0
4           2   1
2           1   2
3           1   2

This may contain errors, im not sure yet, just wanted to show to make sure that pair (3,1) is whther correct with level 2 ? Been thinking on this for quite a while now, I might make some silly mistakes.

Answer 1

Sample data

declare @T table
(
  ParentID int,
  ID int
)

insert into @T values
(NULL,        1),
(1   ,        2),
(1   ,        3),
(2   ,        4)

Recursion from root:

;with C as
(
  select ParentID, ID
  from @T
  where ParentID is null
  union all
  select T.ParentID, T.ID
  from @T as T
    inner join C
      on T.ParentID = C.ID
)
select *
from C

Result

ParentID    ID
----------- -----------
NULL        1
1           2
1           3
2           4

Recursion from leafs:

;with C as
(
  select null as PParentID, ID, ParentID
  from @T
  where ID not in (select ParentID 
                   from @T 
                   where ParentID is not null)
  union all
  select C.ID, T.ID, T.ParentID 
  from @T as T
    inner join C
      on T.ID = C.ParentID 
)
select distinct
       PParentID as ParentID,
       ID
from C

Result:

ParentID    ID
----------- -----------
NULL        3
NULL        4
4           2
2           1
3           1

If you have many branches you will have duplicate rows as merge together. Using distinct takes care of that.

To get the levels correct you need to first calculate the level from top down. Store that in a table variable (or temp table) and then use that as the source for leaf->root recursion.

-- Primary key and unique is in there to get the indexes used in the recursion  
declare @T2 table
(
  ParentID int,
  ID int,
  Level int,
  primary key (ID),
  unique(ParentID, ID)
)

;with C as
(
  select ParentID, ID, 0 as Level
  from @T
  where ParentID is null
  union all
  select T.ParentID, T.ID, Level + 1
  from @T as T
    inner join C
      on T.ParentID = C.ID
)
insert into @T2
select ParentID, ID, Level
from C

;with C as
(
  select null as PParentID, ID, ParentID, Level
  from @T2
  where ID not in (select ParentID 
                   from @T2 
                   where ParentID is not null)
  union all
  select C.ID, T.ID, T.ParentID, T.Level
  from @T2 as T
    inner join C
      on T.ID = C.ParentID 
)
select distinct
       PParentID as ParentID,
       ID,
       max(Level) over() - Level as level
from C

Result:

ParentID    ID          level
----------- ----------- -----------
NULL        3           1
NULL        4           0
2           1           2
3           1           2
4           2           1

It is possible but a really bad idea to replace @T2 with a multi CTE query. It will kill performance because to first CTE will be rebuilt for each recursion. At least that is my guess of what is happening but believe me it is not fast.