Build Traversal path for each BST node

user_9087250 0
Viewed 53

Code to create the table:


    create table BST
    (
        N Int,
        P Int
    )

    insert into BST values 
    (1,3),
    (3,8),
    (4,6),
    (6,3),
    (7,6),
    (8,NULL),
    (10,8),
    (13,14),
    (14,10)

The BST hierarchy looks like this:

enter image description here

I am trying to build a query such that for each node it shows the traversal path needed to reach that particular node.

I tried applying recursive CTE, but I am not sure if I applied it in the correct way or not.


WITH NodeCTE (N, P, [Level])
  AS
(
  SELECT N,
         P,
         1
  FROM BST
  
  WHERE P IS NULL
  
  UNION ALL
  
  SELECT BST.N,
         BST.P,
         NodeCTE.[Level] + 1
  FROM BST
    JOIN NodeCTE ON BST.P = NodeCTE.N
)
SELECT CTE1.N AS Node,
       CTE1.[Level]
FROM NodeCTE CTE1
  LEFT JOIN NodeCTE CTE2 ON CTE1.P = CTE2.N

In the end I need to use STRING_AGG to format the data that is what I found by googling, but I am unable to figure out how to get the data in the format required prior to applying the STRING_AGG

Expected Output:

|   N   |  TraversalPath |
|-------|----------------|
|1      |8->3->1         |
|3      |8->3            |
|4      |8->3->6->4      |
|6      |8->3->6         |
|7      |8->3->6->7      |
|8      |8               |
|10     |8->10           |
|13     |8->10->14->13   |
|14     |8->10->14       |
tsql sql-server sql
1 Answers

You did much of the dirty work, so the additions are minimal:

WITH NodeCTE (N, P, [Level], [path])
AS
(
  SELECT N,
         P,
         1,
         convert(NVARCHAR(MAX),N)
  FROM BST
  WHERE P IS NULL
  UNION ALL
  SELECT BST.N,
         BST.P,
         NodeCTE.[Level] + 1,
         NodeCTE.[path] + '->' + convert(NVARCHAR(MAX),BST.N)
  FROM BST
    JOIN NodeCTE ON BST.P = NodeCTE.N
)
SELECT N,
       P,
       Level,
       path AS Traversal
FROM NodeCTE
ORDER BY N
user_58259630
Related