Generating a Tree Path with a CTE

Download PDF

The following example shows how to create a Tree Path with a Common Table Expression (CTE).

First off what is a tree path?

For this example I will be referring to the product categories at a camping and fitness store, where you have a top level with 4 categories, and some of the categories have subcategories:

  • Camping
    • Tents
      • 1 Person
      • 2 Person
        • Family Camping
        • Backpacking
        • Mountaineering
      • 3 Person
      • 4 Person
    • Backpacks
    • Sleeping Bags
    • Cooking
  • Cycle
  • Snowsports
  • Fitness

 

In this example, the tree path for 2 person mountaineering tents would be  “Camping -> Tents -> 2 Person -> Mountaineering”.  This is sometimes referred to as bread crumbs when you are creating a website or storefront.

 

So how do you get from the following table structure into a hierarchy that includes the Tree Path.

 

You could do it by doing a self JOIN from the table back to itself, joining parent to id, which would work for 2 levels.  Then to go to the third or fourth level, you would need to another one or two self JOINs to get those levels in.  The problem with this strategy is that you are limited on the level of categories or the depth of the tree.

Using a Common Table Expression

The way that I would do it is with a CTE to get the following results.

 

Here is how you do it, with a recursive CTE, which will accommodate any number of levels up to 100 (even more if you specify a deeper MAXRECURSION).

 

WITH departmentcte(deptid, department, parent, LEVEL, treepath) AS

( SELECT id AS deptid, department, parent, 0 AS LEVEL,

CAST(department AS VARCHAR(1024)) AS treepath

FROM departments

WHERE parent IS NULL

UNION ALL — and now for the recursive part 

SELECT d.id AS deptid, d.department, d.parent,

departmentcte.LEVEL + 1 AS LEVEL,

CAST(departmentcte.treepath + ‘ -> ‘ +

CAST(d.department AS VARCHAR(1024))

AS VARCHAR(1024)) AS treepath

FROM departments d

INNER JOIN departmentcte

ON departmentcte.deptid = d.parent)

SELECT *

FROM departmentcte

ORDER BY treepath;

Just another example of using a Recursive Common Table Expression.

For more details, see my CTE presentation at SQL Saturday in Redmond.

Tagged with: , , ,
5 comments on “Generating a Tree Path with a CTE
  1. Mauro says:

    Wow!
    Great example
    Thanks a lot for sharing…
    but..
    how is it possible to show Items according to a Sort Field (on level 0)?

    • SteveStedman SteveStedman says:

      Not sure I understand the question entirely, but you could filter on Level 0, or add another column into the CTE that orders different than what is shown.

      Does that help?

      -Steve

  2. mjak says:

    Hi Steve,

    I have table with columns Id, NodeId, NodeLevel and NodeName (dont have parent id column) and I want now to create a parent id.

    I created a parent id using (Nodelevel-1) but I am not getting the correct result.
    I now want to create a parent id using Id column.

    Could you please help?

    Id Nodeid NodeLevel Nodevalue ParentId
    1 100 1 nodevalue1 0
    2 200 2 nodevalue2 1
    3 300 3 nodevalue3 2
    4 400 4 nodevalue4 3
    5 500 5 nodevalue5 4
    6 600 6 nodevalue6 5
    7 700 6 nodevalue7 5
    8 800 5 nodevalue8 4
    9 900 6 nodevalue9 5
    10 1000 5 nodevalue10 4
    11 1100 6 nodevalue11 5
    12 1200 6 nodevalue12 5
    13 1300 6 nodevalue13 5
    14 1400 6 nodevalue14 5
    15 1500 6 nodevalue15 5
    16 1600 5 nodevalue16 4
    17 1700 6 nodevalue17 5
    18 1800 6 nodevalue18 5
    19 1900 7 nodevalue19 6
    20 2000 7 nodevalue20 6
    21 2100 8 nodevalue21 7
    22 2200 9 nodevalue22 8
    23 2300 9 nodevalue23 8
    24 2400 9 nodevalue24 8
    25 2500 7 nodevalue25 6

    with parentId as (
    select
    Id,
    Nodeid,
    NodeLevel,
    Nodevalue,
    NodeLevel – 1 as ParentId
    from table1)

    , parentnode as (
    select
    Id,
    Nodeid,
    NodeLevel,
    Nodevalue,
    ParentId,
    CAST(NULL as nvarchar(50))as ParentNode,
    CAST(Nodevalue AS nvarchar(1000)) AS [TraversePath],
    0 as TreeLevel
    from parentId as pId
    where NodeLevel = 1
    union all
    select
    pId1.Id,
    pId1.Nodeid,
    pId1.NodeLevel,
    pId1.Nodevalue,
    pId1.ParentId,
    CAST(pn.Nodevalue as nvarchar(50))as ParentNode,
    CAST((pn.[TraversePath] + ‘ -> ‘ + pId1.Nodevalue) AS nvarchar(1000)) AS [TraversePath],
    pn.TreeLevel + 1 as TreeLevel
    from parentId as pId1
    inner join parentnode as pn on pn.Id = pId1.ParentId)

    select * from parentnode
    order by Nodeid

  3. Janet Putnam says:

    Steve,

    Good article, well written and easy to understand. I have a question. If you just wanted the row where department like ‘3 Person’ but still want the whole path how would you do it. I tried replacing the where parent is null with where department like ‘3 Person’ but it didn’t give me the full path.

    I tried adding the where to the final select and while I got the desired results I worry that it has to process the whole cte first and as more data is added (I’m planning on using this for inventory locations) it will get really slow.

    Thanks,

    • SteveStedman SteveStedman says:

      Since this is a recursive CTE it needs to process all levels above it, however it doesn’t have to go wide.

      Adding the where in the final select is the way to go since you don’t know who the parent departments are until you get to the ‘3 person’ department.

      If you knew what the top level department was that this item belonged to you could filter to just those.

      Another way to do this would be to write a CTE where the anchor query was the department you were looking for then recursively search up rather than starting at the top and searching down.

      I hope this helps.

      -Steve Stedman

Leave a Reply

Your email address will not be published. Required fields are marked *

*

Time limit is exhausted. Please reload CAPTCHA.