Hierarchical query in SQL Server 2005

Question

I have a data structure inside a table in SQL Server 2005 representing a chain of related objects. Each object can have replacements in many steps. I want to perform a query that returns all objects and each object's leaf in the replacement chain.

The data:

id  replacement
1   null
2   3
3   null
4   5
5   6
6   null

The result should be:

id  replacement
1   null
2   3
3   null
4   6
5   6
6   null

I believe that a recursive CTE would be a good way to go, but I can't wrap my head around it. A constraints to the problem is that I can't change the data structure, since the database is not in my control.

Answer 1

Have a look at this

DECLARE @Table TABLE(
     ID INT,
     ReplacementID INT
)

INSERT INTO @Table (ID,ReplacementID) SELECT 1, NULL
INSERT INTO @Table (ID,ReplacementID) SELECT 2, 3
INSERT INTO @Table (ID,ReplacementID) SELECT 3, NULL
INSERT INTO @Table (ID,ReplacementID) SELECT 4, 5
INSERT INTO @Table (ID,ReplacementID) SELECT 5, 6
INSERT INTO @Table (ID,ReplacementID) SELECT 6, NULL

INSERT INTO @Table (ID,ReplacementID) SELECT 7, 8
INSERT INTO @Table (ID,ReplacementID) SELECT 8, 9
INSERT INTO @Table (ID,ReplacementID) SELECT 9, 10
INSERT INTO @Table (ID,ReplacementID) SELECT 10, NULL

SELECT * FROM @Table

;WITH repl AS (
    SELECT *, 1 AS Depth
    FROM @Table t
    UNION ALL
    SELECT r.ID,
      t.ReplacementID,
      r.Depth + 1
    FROM repl r INNER JOIN
      @Table t ON r.ReplacementID = t.ID
    WHERE t.ReplacementID IS NOT NULL
)
SELECT  repl.ID,
     repl.ReplacementID
FROM    (
      SELECT ID,
        MAX(Depth) Depth
      FROM repl
      GROUP BY ID
     ) Depths INNER JOIN
     repl ON Depths.ID = repl.ID
       AND Depths.Depth = repl.Depth
ORDER BY 1