# SQL Query for the following structure

Given the following type of data structure.

```    ID  NAME  TREELEFT  TREERIGHT  PARENT
1   XYZ       1         2         0
2   ABC       3         6         0
3   DEF       4         5         2
4   HIJ       7         10        0
5   KLM       8         9         4
6   NOP       11        16        0
7   QRS       12        15        6
8   TUV       13        14        7
```

The methodology is more or less identical to the nested set model except I've included a parent, just to make my life a little easier. (https://en.wikipedia.org/wiki/Nested_set_model#Example) I need to come up with a way of detecting gaps. For example if ID=6 had a different treeright say 17. There would technically be a gap of 1.

For the moment I've done this in a series of different queries.

One to detect if treeright doesn't exceed 2n, another to detect if treeright is always > than treeleft. Another couple to ensure that no treelefts or treerights are identical to each other.

However if I could add just check to ensure that the tree had no gaps I'm sure a couple of the other tests would become redundant. Can anyone think of a good way to do this. I've been racking my brain on this one for quite a long period of time.

-
So basically you want to know if a btree is broken, and therefore a gap in select val from (select treeleft as val from treetable union all select treeright as val from treetable) order by val ? – Phil Oct 17 '12 at 17:11
@Phil Yes I want to see if the btree is broken. What would be the query given the union that will detect a gap? – Mark D Oct 23 '12 at 3:16

## 1 Answer

It took me a while to figure this one out.

``````        SELECT  t1.id      + 1 AS `start`,
MIN(t3.id) - 1 AS `stop`
FROM (SELECT  table1.id
FROM (SELECT treeleft  AS id FROM structure
UNION ALL
SELECT treeright AS id FROM structure
)
AS  table1)
AS t1
LEFT OUTER JOIN (SELECT  table2.id
FROM (SELECT treeleft  AS id FROM structure
UNION ALL
SELECT treeright AS id FROM structure
)
AS  table2)
AS  t2
ON  t1.id = t2.id - 1
LEFT OUTER JOIN (SELECT  table3.id
FROM (SELECT treeleft  AS id FROM structure
UNION ALL
SELECT treeright AS id FROM structure
)
AS  table3)
AS  t3
ON  t1.id < t3.id
WHERE  t2.id IS NULL
AND  t3.id IS NOT NULL
GROUP BY  t1.id,
t2.id;
``````
-