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.
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 &lt; t3.id
          WHERE  t2.id IS NULL 
            AND  t3.id IS NOT NULL
       GROUP BY  t1.id, 
                 t2.id;