# Convert Tree Structure From Nested Set Into Adjacency List

Tree structures are often represented in nested set model or adjacency list model. In the nested set model each node has a left and right, where the root will always have a 1 in its left column and twice the number of nodes in its right column. On the other side the adjacency list model uses a linking column (child/parent) to handle hierarchies.

Sometimes there is a need to convert a nested set model into an adjacency list model. Here is one example of doing that:

`CREATE TABLE NestedSet ( node CHAR(1) NOT NULL PRIMARY KEY, lf INT NOT NULL, rg INT NOT NULL); INSERT INTO NestedSet VALUES ('A', 1, 8);INSERT INTO NestedSet VALUES ('B', 2, 3);INSERT INTO NestedSet VALUES ('C', 4, 7);INSERT INTO NestedSet VALUES ('D', 5, 6); CREATE TABLE AdjacencyList ( node CHAR(1) NOT NULL PRIMARY KEY, parent CHAR(1) NULL); INSERT INTO AdjacencyListSELECT A.node,       B.node AS parentFROM NestedSet AS ALEFT OUTER JOIN NestedSet AS B  ON B.lf = (SELECT MAX(C.lf)             FROM NestedSet AS C             WHERE A.lf > C.lf               AND A.lf < C.rg);-- Resultsnode    parent------  --------A       NULLB       AC       AD       C`

Book: “Trees and Hierarchies in SQL for Smarties” by Joe Celko

Tags:
5 replies
1. Unity Web says:

Exactly what I was looking for. Thank you very much !

2. mrbinky3000 says:

What about going the other way?

3. Plamen Ratchev says:

Hi mrbinky3000,

Here is one method to convert adjacency list to nested sets (credit goes to Itzik Ben-Gan):

WITH Nums AS (
SELECT n FROM(VALUES(1),(2)) AS T(n)),
SortPath AS (
SELECT node, 0 AS lvl, n,
CAST(n AS VARBINARY(MAX)) AS sort_path
CROSS JOIN Nums
WHERE parent IS NULL
UNION ALL
SELECT A.node, P.lvl + 1, N.n,
P.sort_path + CAST(
ROW_NUMBER() OVER(PARTITION BY A.parent
ORDER BY A.node, N.n)
AS BINARY(4))
FROM SortPath AS P
ON P.n = 1
AND A.parent = P.node
CROSS JOIN Nums AS N),
Sort AS (
SELECT node, lvl,
ROW_NUMBER() OVER(ORDER BY sort_path) AS sortval
FROM SortPath),
NS AS (
SELECT node, lvl, MIN(sortval) AS lf, MAX(sortval) AS rg
FROM Sort
GROUP BY node, lvl)
SELECT A.node, NS.lvl, NS.lf, NS.rg
FROM NS
ON A.node = NS.node;

4. Darshan Shroff says:

The above sql seems to be incomplete and does not work.

5. 