## Hierarchies with CTEs

Common table expressions (CTEs) have many applications. However, one of their capabilities to implement recursive queries is very useful for navigating and manipulating hierarchies.

Here is one brief example of utilizing that. Given a table with employees and their managers represented as adjacency list, provide list of employees that report to particular manager, ordered by the natural hierarchy order of listing each employee under the corresponding manager.

`-- Create sample table with employees and managersCREATE TABLE Employees( employee_nbr INT NOT NULL PRIMARY KEY, employee_name VARCHAR(35), manager_nbr INT NULL REFERENCES Employees(employee_nbr)); INSERT INTO Employees VALUES (1, 'John Doe', NULL);INSERT INTO Employees VALUES (2, 'James Brown', 1);INSERT INTO Employees VALUES (3, 'Keith Green', NULL);INSERT INTO Employees VALUES (4, 'Peter Roth', 2);INSERT INTO Employees VALUES (5, 'Hans Gruber', 2);INSERT INTO Employees VALUES (6, 'Kris Evans', 4);INSERT INTO Employees VALUES (7, 'Jeff Colleman', NULL); -- Use recursive CTE to build binary and charachter pathsWITH EmployeeHierarchyAS(SELECT employee_nbr, employee_name, manager_nbr,        CAST(employee_nbr AS VARBINARY(MAX)) AS bpath,        CAST('.' +              CAST(employee_nbr AS VARCHAR(4)) +             '.' AS VARCHAR(MAX)) AS cpath FROM Employees WHERE manager_nbr IS NULL UNION ALL SELECT E.employee_nbr, E.employee_name, E.manager_nbr,        H.bpath + CAST(E.employee_nbr AS BINARY(4)),        H.cpath + CAST(E.employee_nbr AS VARCHAR(4)) + '.' FROM Employees AS E JOIN EmployeeHierarchy AS H   ON E.manager_nbr = H.employee_nbr)SELECT employee_nbr, employee_name, manager_nbr, bpath, cpathFROM EmployeeHierarchyWHERE cpath LIKE '%.2.%' -- filter all employees for manager 2ORDER BY bpath;          -- order by natural hierarchy path -- Resultsemployee_nbr employee_name  manager_nbr bpath                              cpath------------ -------------- ----------- ---------------------------------- ----------2            James Brown    1           0x0000000100000002                 .1.2.4            Peter Roth     2           0x000000010000000200000004         .1.2.4.6            Kris Evans     4           0x00000001000000020000000400000006 .1.2.4.6.5            Hans Gruber    2           0x000000010000000200000005         .1.2.5.`

The method above creates two manager/employee paths: a binary path that preserves the natural ordering at each level, which can be used to sort; a character path that can be used to filter by manager.

## 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`