Generating string tree branches from father-children table

Question

I have a father-children table like the following:

child   |   father
H       :   G
F       :   G
G       :   D
E       :   D
A       :   E
B       :   C
C       :   E

I'd like sql server to generate something like this (as it was asked in this question Convert a series of parent-child relationships into a hierarchical tree? but in tsql and not in php):

 D
 ├── E
 │   ├── C
 │   │   └── B
 │   └── A   
 └── G
     ├── F
     └── H

Of course the result can be a string column that i can copy in an text editor.

I'd like also to have a second query that generate something like this:

 father |   descendants
 D      |   D -> E -> C -> B
 D      |   D -> E -> A
 D      |   D -> G -> F
 D      |   D -> G -> H

In the previous case there is just one tree with a single father but in the table there could be more the one with multiple fathers, like this tree would be if D would not exist.

If the first part of the requast (the pseudo visual tree) is not possible to do it's fine. The important part is the table.

I've tried to do something like this for long bu i could not attain the wanted results.

TNX

Answer 1

This is interesting. It's probably inefficient to do it in SQL rather than some other language, though. Still fun to think about.

Here's how I did it.

Initialising the table:

SET NOCOUNT ON
DECLARE @Table TABLE ([Child] NVARCHAR(10), [Parent] NVARCHAR(10))
INSERT @Table VALUES ('H','G'),('F','G'),('G','D'),('E','D')
,('A','E'),('B','C'),('C','E'),('D', NULL),('Z','E'),('X','Z'),('Y','Z')
,('L',NULL),('M','L'),('N','L'),('P','N'),('Q','L'), ('R',NULL),('S', 'R')
IF OBJECT_ID('tempdb..#tmptable') IS NOT NULL DROP TABLE #tmptable
; WITH T AS (
    SELECT Parent, Child, 1 [Level]
    FROM @Table
    WHERE Parent IS NULL
    UNION ALL
    SELECT a.Parent, a.Child, T.[Level] + 1
    FROM @Table a
    JOIN T ON a.Parent = T.Child)
SELECT *
INTO #tmptable
FROM T

For Query 1, I'm using dynamic SQL under the assumption you don't know the maximum amount of descendants any given parent could have:

DECLARE @SQL NVARCHAR(MAX)
DECLARE @a INT = (SELECT MAX(Level) FROM #tmptable)
DECLARE @b INT = 2
SET @SQL = 
'; WITH CTE AS (
    SELECT T1.Child Father'
WHILE @b<= @a BEGIN
    SET @SQL += '
        , ISNULL(T' + CONVERT(NVARCHAR, @b) + '.Child, '''') Child' + CONVERT(NVARCHAR, @b - 1)
    SET @b += 1
END
SET @SQL +='
        , ROW_NUMBER() OVER (ORDER BY T1.Child'
SET @b =  2 
WHILE @b <= @a BEGIN        
    SET @SQL += ', T' + CONVERT(NVARCHAR, @b) + '.Child'
    SET @b += 1
END
SET @SQL += ') RN
    FROM #tmptable T1'
SET @b = 2
WHILE @b <= @a BEGIN
    SET @SQL += '
    LEFT JOIN #tmptable T' + CONVERT(NVARCHAR, @b) + ' ON T' + CONVERT(NVARCHAR, @b) +'.Parent = T' + CONVERT(NVARCHAR, @b - 1) + '.Child'
    SET @b += 1
END
SET @SQL += '
    WHERE T1.Parent IS NULL
    GROUP BY T1.Child'
SET @b = 2
WHILE @b <= @a BEGIN
    SET @SQL += ', T' + CONVERT(NVARCHAR, @b) + '.Child'
    SET @b += 1
END
SET @SQL += ')
SELECT ''<ul>'' + REPLACE(REPLACE(CONVERT(NVARCHAR(MAX), (
    SELECT CASE WHEN RN = 1 THEN ''<li>''
            WHEN (SELECT Father FROM CTE WHERE RN = C.RN - 1) <> Father THEN ''<li>''
            ELSE '''' END --Fatherli
        , CASE WHEN RN = 1 THEN Father
            WHEN (SELECT Father FROM CTE WHERE RN = C.RN - 1) <> Father THEN Father
            ELSE '''' END --Father
        , CASE WHEN RN = 1 THEN ''</li>''
            WHEN (SELECT Father FROM CTE WHERE RN = C.RN - 1) <> Father THEN ''</li>''
            ELSE '''' END --Fathercli
        , CASE WHEN RN = 1 AND Child1 <> '''' THEN ''<ul>''
            WHEN (SELECT Father FROM CTE WHERE RN = C.RN - 1) <> Father AND Child1 <> '''' THEN ''<ul>''
            ELSE '''' END --Fatherul'
SET @b = 2
WHILE @b <= @a BEGIN
    SET @SQL += '
        , CASE WHEN RN = 1 AND Child' + CONVERT(NVARCHAR, @b-1) + ' <> '''' THEN ''<li>''
            WHEN (SELECT Child' + CONVERT(NVARCHAR, @b-1) + ' FROM CTE WHERE RN = C.RN - 1) <> Child' + CONVERT(NVARCHAR, @b-1) + ' AND Child' + CONVERT(NVARCHAR, @b-1) + ' <> '''' THEN ''<li>''
            ELSE '''' END --Child' + CONVERT(NVARCHAR, @b-1) + 'li
        , CASE WHEN RN = 1 AND Child' + CONVERT(NVARCHAR, @b-1) + ' <> '''' THEN Child' + CONVERT(NVARCHAR, @b-1) + '
            WHEN (SELECT Child' + CONVERT(NVARCHAR, @b-1) + ' FROM CTE WHERE RN = C.RN - 1) <> Child' + CONVERT(NVARCHAR, @b-1) + ' AND Child' + CONVERT(NVARCHAR, @b-1) + ' <> '''' THEN Child' + CONVERT(NVARCHAR, @b-1) + '
            ELSE '''' END --Child' + CONVERT(NVARCHAR, @b-1) + '
        , CASE WHEN RN = 1 AND Child' + CONVERT(NVARCHAR, @b-1) + ' <> '''' THEN ''</li>''
            WHEN (SELECT Child' + CONVERT(NVARCHAR, @b-1) + ' FROM CTE WHERE RN = C.RN - 1) <> Child' + CONVERT(NVARCHAR, @b-1) + ' AND Child' + CONVERT(NVARCHAR, @b-1) + ' <> '''' THEN ''</li>''
            ELSE '''' END --Child' + CONVERT(NVARCHAR, @b-1) + 'cli'
    IF @a <> @b 
        SET @SQL += '
        , CASE WHEN RN = 1 AND Child' + CONVERT(NVARCHAR, @b-1) + ' <> '''' AND Child' + CONVERT(NVARCHAR, @b) + ' <> '''' THEN ''<ul>''
            WHEN (SELECT Child' + CONVERT(NVARCHAR, @b-1) + ' FROM CTE WHERE RN = C.RN - 1) <> Child' + CONVERT(NVARCHAR, @b-1) + ' AND Child' + CONVERT(NVARCHAR, @b) + ' <> '''' THEN ''<ul>''
            ELSE '''' END --Child' + CONVERT(NVARCHAR, @b-1) + 'ul'
    SET @b += 1
END
SET @b -= 3
WHILE @b > 0 BEGIN
    SET @SQL += '
        , CASE WHEN RN = (SELECT MAX(RN) FROM CTE) AND Child' + CONVERT(NVARCHAR, @b+1) + ' <> '''' THEN ''</ul>''
            WHEN (SELECT Child' + CONVERT(NVARCHAR, @b) + ' FROM CTE WHERE RN = C.RN + 1) <> Child' + CONVERT(NVARCHAR, @b) + ' AND Child' + CONVERT(NVARCHAR, @b+1) + ' <> '''' THEN ''</ul>''
            ELSE '''' END --Child' + CONVERT(NVARCHAR, @b) + 'cul'
    SET @b -= 1
END
SET @SQL += '
        , CASE WHEN RN = (SELECT MAX(RN) FROM CTE) AND Child1 <> '''' THEN ''</ul>''
            WHEN (SELECT Father FROM CTE WHERE RN = C.RN + 1) <> Father AND Child1 <> '''' THEN ''</ul>''
            ELSE '''' END --Fathercul
    FROM CTE C
    FOR XML PATH (''''))), ''&lt;'', ''<''), ''&gt;'', ''>'') + ''</ul>'''
EXEC(@SQL)
-- PRINT @SQL

The output (for the values I input) is <ul><li>D</li><ul><li>E</li><ul><li>A</li><li>C</li><ul><li>B</li></ul><li>Z</li><ul><li>X</li><li>Y</li></ul></ul><li>G</li><ul><li>F</li><li>H</li></ul></ul><li>L</li><ul><li>M</li><li>N</li><ul><li>P</li></ul><li>Q</li></ul><li>R</li><ul><li>S</li></ul></ul> which displays as such:

• D
• E
• A
• C
• B
• Z
• X
• Y
• G
• F
• H
• L
• M
• N
• P
• Q
• R
• S

For the second query, there are probably easier ways to do it, but I figured why not go with more dynamic SQL?

DECLARE @i INT = (SELECT MAX([Level]) FROM #tmptable), @j INT = 2
DECLARE @SQL2 NVARCHAR(MAX)
SET @SQL2 = 'SELECT T1.Child Father, T1.Child '
WHILE @j <= @i BEGIN
    SET @SQL2 += '+ ISNULL('' -> '' + T' + CONVERT(NVARCHAR, @j) + '.Child, '''')'
    SET @j += 1
END
SET @j = 2
SET @SQL2 += ' Descendants FROM #tmptable T1'
WHILE @j <= @i BEGIN
    SET @SQL2 += ' LEFT JOIN #tmptable T' + CONVERT(NVARCHAR, @j) + ' ON T' + CONVERT(NVARCHAR, @j) + '.[Parent] = T' + CONVERT(NVARCHAR, @j-1) + '.[Child]'
    SET @j += 1
END
SET @j = 2
SET @SQL2 += ' WHERE T1.[Parent] IS NULL ORDER BY T1.[Child]'
WHILE @j <= @i BEGIN
    SET @SQL2 += ', T' + CONVERT(NVARCHAR, @j) + '.[Child]'
    SET @j += 1
END
EXEC(@SQL2)

Answer 2

To avoid scanning entire table for greatest ancestor I would add row with father = NULL or any value that will indicate it.

To get path from ancestor to leaf you can use CTE:

CREATE TABLE #tab(
   child  VARCHAR(8) NOT NULL PRIMARY KEY
  ,father VARCHAR(4) NULL
);
INSERT INTO #tab(child,father) VALUES ('H','G');
INSERT INTO #tab(child,father) VALUES ('F','G');
INSERT INTO #tab(child,father) VALUES ('G','D');
INSERT INTO #tab(child,father) VALUES ('E','D');
INSERT INTO #tab(child,father) VALUES ('A','E');
INSERT INTO #tab(child,father) VALUES ('B','C');
INSERT INTO #tab(child,father) VALUES ('C','E');

INSERT INTO #tab(child,father) VALUES ('D',NULL);  -- add by me

INSERT INTO #tab(child,father) VALUES ('Z',NULL);  -- for testing
INSERT INTO #tab(child,father) VALUES ('Z1','Z');
INSERT INTO #tab(child,father) VALUES ('Z2','Z');

Query:

;WITH cte AS
(
  SELECT 
       Child
      ,Father
      ,Level = 1
      ,Path = CAST(Child AS NVARCHAR(MAX))
      ,Ancestor = Child
  FROM #tab
  WHERE father IS NULL
  UNION ALL 
  SELECT
       t.Child
      ,t.Father
      ,Level = Level + 1
      ,Path = c.Path + ' -> ' + t.Child
      ,c.Ancestor
  FROM #tab t
  JOIN cte c
    ON t.Father = c.Child
)
SELECT Father = c.Ancestor
       ,c.Path
FROM cte c
LEFT JOIN cte c2
  ON c2.Path LIKE c.Path + ' -> ' +  '%'
WHERE c2.Path IS NULL;

LiveDemo

This is classic usage of recursive CTE with added two fields: Path from Ancestor to leaf and Ancestor. Then you need to self join result and use LIKE to filter out only leaf nodes based on Path.