SQL query to find empty nodes in a tree structure table

user_3576968 0
Viewed 190

I'm developing an Android application that stores some of its data as a tree like structure in an SQLite table.

As an example, the relevant part of the table has the following structure:

id name type depth parentId
1 1 node 0
2 2 node 1 1
3 3 node 1 1
4 4 node 2 2
5 5 node 2 3
6 6 node 2 3
7 7 node 3 4
8 8 node 3 6
9 ** data 2 2
10 ** data 2 2
11 ** data 3 4
12 ** data 3 5

The following image represents the same data of the table:

Tree structure in the table

The question is: How can I get all the nodes (type = node) that have no data structures below them? In the example the result would be nodes 6, 7 and 8 which are colored green in the tree.

For now, I'm only able to get empty nodes on the deepest part of the tree with the following query:

SELECT id
FROM treeTable
WHERE type = 'node'
    AND id NOT IN
        (SELECT DISTINCT parentId
        FROM treeTable
        WHERE parentId IS NOT NULL)

My problem is with that node number 6. It should be returned in the query but, as it appears as a parent of another node I don't know how to filter it out. Any ideas are welcome.

sqlite sql
2 Answers

After some research based on the @tinazmu's answer, I finally came up with a query that seems to be working fine for my case in SQLite.

WITH AncestryTree AS (
    SELECT id, parentId, type
    FROM Tree
    WHERE parentId IS NOT NULL

    UNION ALL

    SELECT T.id, AT.parentId, T.type
    FROM AncestryTree AT
        JOIN Tree T ON AT.id = T.parentId
)

SELECT id
FROM Tree
WHERE type = 'node'
    AND id NOT IN (
        SELECT DISTINCT parentId
        FROM AncestryTree
        WHERE type = 'data'
    )

The query can be tested in db-fiddle, but it'd be great if someone pointed out any flaws or optimizations to this query.

user_35769680

I could use recursion to find the data nodes within each 'node' node. The first one is for SqlServer:

with treeTable as (
select *
from (values 
 (1,'1','node',0,null)
,(2,'2','node',1,1)
,(3,'3','node',1,1)
,(4,'4','node',2,2)
,(5,'5','node',2,3)
,(6,'6','node',2,3)
,(7,'7','node',3,4)
,(8,'8','node',3,6)
,(9,'**','data',2,2)
,(10,'**','data',2,2)
,(11,'**','data',3,4)
,(12,'**','data',3,5)
) T(id, name,   type,   depth,  parentId)
),
Hry as (
 SELECT StartNode=TN.id, ThisNode=TN.id, TN.name, tn.type, tn.depth, L=0
 FROM treeTable TN
 union all
 SELECT StartNode=H.StartNode, ThisNode=TN.id, TN.name, TN.type, TN.depth, L=L+1
 FROM treeTable TN
      inner join 
      Hry H
      on H.ThisNode=TN.ParentId
)
/* Now repeat for each 'node' node: recursively traverse each sub-tree and see if there are data nodes underneath */
select T.id
from treeTable T
     left join
     Hry H
     on T.id=H.StartNode
     and H.type='data'
where T.type='node'
and H.StartNode is null

For Sqlite

with treeTable as (
    select  1 as id, '1'as name,'node' as type,0 as depth ,null as parentID union all
    select  2 as id, '2'as name,'node' as type,1 as depth ,   1 as parentID union all
    select  3 as id, '3'as name,'node' as type,1 as depth ,   1 as parentID union all
    select  4 as id, '4'as name,'node' as type,2 as depth ,   2 as parentID union all
    select  5 as id, '5'as name,'node' as type,2 as depth ,   3 as parentID union all
    select  6 as id, '6'as name,'node' as type,2 as depth ,   3 as parentID union all
    select  7 as id, '7'as name,'node' as type,3 as depth ,   4 as parentID union all
    select  8 as id, '8'as name,'node' as type,3 as depth ,   6 as parentID union all
    select  9 as id,'**'as name,'data' as type,2 as depth ,   2 as parentID union all
    select 10 as id,'**'as name,'data' as type,2 as depth ,   2 as parentID union all
    select 11 as id,'**'as name,'data' as type,3 as depth ,   4 as parentID union all
    select 12 as id,'**'as name,'data' as type,3 as depth ,   5 as parentID 
),
Hry as (
 SELECT TN.id as StartNode, TN.id as ThisNode, TN.name, tn.type, tn.depth, 0 as L
 FROM treeTable TN
 union all
 SELECT H.StartNode as StartNode, TN.id as ThisNode, TN.name, TN.type, TN.depth, L+1 as L
 FROM treeTable TN
      inner join 
      Hry H
      on H.ThisNode=TN.ParentId
)
/* Now repeat for each 'node' node: recursively traverse each sub-tree and see if there are data nodes underneath */
select T.id
from treeTable T
     left join
     Hry H
     on T.id=H.StartNode
     and H.type='data'
where T.type='node'
and H.StartNode is null
user_116950490
Related