CTE Recursion to get tree hierarchy

Question

I need to get an ordered hierarchy of a tree, in a specific way. The table in question looks a bit like this (all ID fields are uniqueidentifiers, I've simplified the data for sake of example):

EstimateItemID    EstimateID    ParentEstimateItemID     ItemType
--------------    ----------    --------------------     --------
       1              A                NULL              product
       2              A                  1               product
       3              A                  2               service
       4              A                NULL              product
       5              A                  4               product
       6              A                  5               service
       7              A                  1               service
       8              A                  4               product

Graphical view of the tree structure (* denotes 'service'):

           A
       ___/ \___
      /         \
    1            4
   / \          / \
  2   7*       5   8
 /            /
3*           6*

Using this query, I can get the hierarchy (just pretend 'A' is a uniqueidentifier, I know it isn't in real life):

DECLARE @EstimateID uniqueidentifier
SELECT @EstimateID = 'A'

;WITH temp as(
    SELECT * FROM EstimateItem
    WHERE EstimateID = @EstimateID

    UNION ALL

    SELECT ei.* FROM EstimateItem ei
    INNER JOIN temp x ON ei.ParentEstimateItemID = x.EstimateItemID
)

SELECT * FROM temp

This gives me the children of EstimateID 'A', but in the order that it appears in the table. ie:

EstimateItemID
--------------
      1
      2
      3
      4
      5
      6
      7
      8

Unfortunately, what I need is an ordered hierarchy with a result set that follows the following constraints:

1. each branch must be grouped
2. records with ItemType 'product' and parent are the top node 
3. records with ItemType 'product' and non-NULL parent grouped after top node 
4. records with ItemType 'service' are bottom node of a branch

So, the order that I need the results, in this example, is:

EstimateItemID
--------------
      1
      2
      3
      7
      4
      5
      8
      6

What do I need to add to my query to accomplish this?

Answer 1

Check this:

DECLARE @hl NVARCHAR(1)=NCHAR(9474),@hs NVARCHAR(1)=NCHAR(12288),@hb NVARCHAR(1)=NCHAR(9500),@hc NVARCHAR(1)=NCHAR(9492),@hd NVARCHAR(1)=' '; DECLARE @ItemID NVARCHAR(MAX)='A';

WITH ds AS( SELECT * FROM (VALUES ('A',NULL,'Product'),('1','A','Product'),('4','A','Service'),('2','1','Product'),('7*','1','Service'),('3','2','Product'), ('5','4','Product'),('8','4','Service'),('6*','5','Product'))t(Node_n, Parent_n, ItemType)

),H0 AS( SELECT HIERARCHYID::GetRoot()[h_id],@ItemID[Node_n]

),H1 AS( SELECT CAST(b.h_id.ToString()+RTRIM(ROW_NUMBER()OVER(ORDER BY parent_n))+'/'AS HIERARCHYID)[h_id],a.Node_n FROM ds a INNER JOIN H0 b ON a.parent_n=b.Node_n UNION ALL SELECT CAST(b.h_id.ToString()+RTRIM(ROW_NUMBER()OVER(ORDER BY parent_n))+'/'AS HIERARCHYID)[h_id],a.Node_n FROM ds a INNER JOIN H1 b ON a.parent_n=b.Node_n

),H2 AS( SELECT * FROM H0 a UNION ALL SELECT * FROM H1 a

),T0 AS( SELECT a.h_id,CASE WHEN EXISTS(SELECT * FROM H1 WHERE h_id>b.h_id AND h_id.GetAncestor(1)=b.h_id.GetAncestor(1))THEN @hl ELSE @hs END[t_l] FROM H1 a INNER JOIN H1 b ON a.h_id.IsDescendantOf(b.h_id)=1

),T1 AS( SELECT x.*,(SELECT t_l+'' FROM T0 WHERE h_id=x.h_id FOR XML PATH(''))[b_tree] FROM H2 x)

SELECT ISNULL(LEFT(b_tree,LEN(b_tree)-1)+CASE WHEN EXISTS (SELECT * FROM H2 WHERE h_id>a.h_id AND h_id.GetAncestor(1)=a.h_id.GetAncestor(1)) THEN @hb ELSE @hc END+@hd,'')+RTRIM(a.Node_n)[BOM_Tree], a.h_id, a.Node_n FROM T1 a ORDER BY a.h_id

Result

Answer 2

I believe that you need to add the following to the results of your CTE...

1. BranchID = some kind of identifier that uniquely identifies the branch. Forgive me for not being more specific, but I'm not sure what identifies a branch for your needs. Your example shows a binary tree in which all branches flow back to the root.
2. ItemTypeID where (for example) 0 = Product and 1 = service.
3. Parent = identifies the parent.

If those exist in the output, I think you should be able to use the output from your query as either another CTE or as the FROM clause in a query. Order by BranchID, ItemTypeID, Parent.

Answer 3

This is an add-on to Fabio's great idea from above. Like I said in my reply to his original post. I have re-posted his idea using more common data, table name, and fields to make it easier for others to follow.

Thank you Fabio! Great name by the way.

First some data to work with:

CREATE TABLE tblLocations (ID INT IDENTITY(1,1), Code VARCHAR(1), ParentID INT, Name VARCHAR(20));

INSERT INTO tblLocations (Code, ParentID, Name) VALUES
('A', NULL, 'West'),
('A', 1, 'WA'),
('A', 2, 'Seattle'),
('A', NULL, 'East'),
('A', 4, 'NY'),
('A', 5, 'New York'),
('A', 1, 'NV'),
('A', 7, 'Las Vegas'),
('A', 2, 'Vancouver'),
('A', 4, 'FL'),
('A', 5, 'Buffalo'),
('A', 1, 'CA'),
('A', 10, 'Miami'),
('A', 12, 'Los Angeles'),
('A', 7, 'Reno'),
('A', 12, 'San Francisco'),
('A', 10, 'Orlando'),
('A', 12, 'Sacramento');

Now the recursive query:

-- Note: The 'Code' field isn't used, but you could add it to display more info.
;WITH MyCTE AS (
  SELECT ID, Name, 0 AS TreeLevel, CAST(ID AS VARCHAR(255)) AS TreePath
  FROM tblLocations T1
  WHERE ParentID IS NULL

  UNION ALL

  SELECT T2.ID, T2.Name, TreeLevel + 1, CAST(TreePath + '.' + CAST(T2.ID AS VARCHAR(255)) AS VARCHAR(255)) AS TreePath
  FROM tblLocations T2
  INNER JOIN MyCTE itms ON itms.ID = T2.ParentID
)
-- Note: The 'replicate' function is not needed. Added it to give a visual of the results.
SELECT ID, Replicate('.', TreeLevel * 4)+Name 'Name', TreeLevel, TreePath
FROM  MyCTE 
ORDER BY TreePath;

Answer 4

Try this:

;WITH items AS (
    SELECT EstimateItemID, ItemType
    , 0 AS Level
    , CAST(EstimateItemID AS VARCHAR(255)) AS Path
    FROM EstimateItem 
    WHERE ParentEstimateItemID IS NULL AND EstimateID = @EstimateID

    UNION ALL

    SELECT i.EstimateItemID, i.ItemType
    , Level + 1
    , CAST(Path + '.' + CAST(i.EstimateItemID AS VARCHAR(255)) AS VARCHAR(255))
    FROM EstimateItem i
    INNER JOIN items itms ON itms.EstimateItemID = i.ParentEstimateItemID
)

SELECT * FROM items ORDER BY Path

With Path - rows a sorted by parents nodes

If you want sort childnodes by ItemType for each level, than you can play with Level and SUBSTRING of Pathcolumn....

Here SQLFiddle with sample of data