Find lowest common parent in recursive SQL table

common-table-expression, recursion, sql, sql-server, t-sql

Solution

After doing some thinking and some hints in the right direction from Marc's answer (thanks), I came up with another solution myself:

DECLARE @parentChild TABLE (Id INT NOT NULL, ParentId INT NULL);
INSERT INTO @parentChild VALUES (1, NULL);
INSERT INTO @parentChild VALUES (2, 1);
INSERT INTO @parentChild VALUES (3, 1);
INSERT INTO @parentChild VALUES (4, 2);
INSERT INTO @parentChild VALUES (5, 2);
INSERT INTO @parentChild VALUES (6, 3);
INSERT INTO @parentChild VALUES (7, 3);
INSERT INTO @parentChild VALUES (8, 7);

DECLARE @ids TABLE (Id INT NOT NULL);
INSERT INTO @ids VALUES (6);
INSERT INTO @ids VALUES (7);
INSERT INTO @ids VALUES (8);

DECLARE @count INT;
SELECT @count = COUNT(1) FROM @ids;

WITH Nodes(Id, ParentId, Depth) AS
(
    -- Start from every node in the @ids collection.
    SELECT pc.Id , pc.ParentId , 0 AS DEPTH
    FROM @parentChild pc
    JOIN @ids i ON pc.Id = i.Id

    UNION ALL

    -- Recursively find parent nodes for each starting node.
    SELECT pc.Id , pc.ParentId , n.Depth - 1
    FROM @parentChild pc
    JOIN Nodes n ON pc.Id = n.ParentId
)
SELECT n.Id
FROM Nodes n
GROUP BY n.Id
HAVING COUNT(n.Id) = @count
ORDER BY MIN(n.Depth) DESC

It now returns the entire path from the lowest common parent to the root node but that is a matter of adding a `TOP 1` to the select.

Problem

Suppose I have a recursive table (e.g. employees with managers) and a list of size `0..n` of ids. How can I find the lowest common parent for these ids? For example, if my table looks like this: ``` Id | ParentId ---|--------- 1 | NULL 2 | 1 3 | 1 4 | 2 5 | 2 6 | 3 7 | 3 8 | 7 ``` Then the following sets of ids lead to the following results (the first one is a corner case): ``` [] => 1 (or NULL, doesn't really matter) [1] => 1 [2] => 2 [1,8] => 1 [4,5] => 2 [4,6] => 1 [6,7,8] => 3 ``` How to do this? EDIT: Note that parent isn't the correct term in all cases. It's the lowest common node in all paths up the tree. The lowest common node can also be a node itself (for example in the case `[1,8] => 1`, node `1` is not a parent of node `1` but node `1` itself). Kind regards, Ronald

Original source