CODEWITHSUNDEEP
sqlt-sqlcommon-table-expression
Gwinn
Gwinn

Reputation: 1368

Return lowest level nodes (leafs) with topmost level nodes (roots)

I would like to get all the leafs and their roots from a hierarchy table. A leaf is the lowest level node and a root is the topmost level node.

Given a tree like:

A
--B
  --C
  --D
E
--F
--G
  --H

Leafs are nodes: C, D Roots are: A, E

The table looks like (I've put parent names in parenthesis for clarity):

Id | Parent | Name
0  | NULL   | A
1  | 0 (A)  | B
2  | 1 (B)  | C
3  | 1 (B)  | D
4  | NULL   | E
5  | 4 (E)  | F
6  | 4 (E)  | G
7  | 6 (G)  | H

The result I'm looking for is:

Id | Parent | Name
2  | 0 (A)  | C
3  | 0 (A)  | D
5  | 4 (E)  | F
7  | 4 (E)  | H

I've already setup the following CTE query that is able to find all the roots for every leaf.

WITH Tree (Id, [Name], Parent) AS
(

      SELECT

            Id, [Name], Parent

      FROM

            dbo.Department

      WHERE 
           --Every leaf node, that is: a node that is never a parent
           Id IN (

            SELECT Id
            FROM Department
            WHERE Id NOT IN (
                SELECT Parent FROM Department
                WHERE Parent IS NOT NULL
            ))


      UNION ALL 

      SELECT

            dept.Id, dept.[Name], dept.Parent

      FROM

            dbo.Department dept

      INNER JOIN Tree ON 

            dept.Id = Tree.Parent

)
SELECT * FROM Tree
WHERE Parent IS NULL

But I have no idea how to add leafs id to the result along with its root.

Upvotes: 3

Views: 378

Answers (1)

Shawn
Shawn

Reputation: 52449

Something like

WITH cte(id, name, root) AS
  (SELECT id, name, id FROM department WHERE parent IS NULL
   UNION ALL
   SELECT d.id, d.name, root
   FROM department AS d
   JOIN cte AS c ON d.parent = c.id)
SELECT id, root, name
FROM cte AS c
WHERE NOT EXISTS (SELECT 1 FROM department AS d WHERE c.id = d.parent)
ORDER BY id;

will give you all the leaves and their roots:

id          root        name      
----------  ----------  ----------
2           0           C         
3           0           D         
5           4           F         
7           4           H

db<>fiddle example

The trick is to have a column in the cte that starts out as the id of each root that's passed through unchanged to each child, grandchild, etc. in turn. Then just filter out the non-leaf rows.

Upvotes: 3

Related Questions