How to Determine the Type of Tree Nodes using SQL?

Given a Relational Table stroing the nodes in a tree-like data structure, like this:

+----+------+
| id | p_id |
+----+------+
| 1  | null |
| 2  | 1    |
| 3  | 1    |
| 4  | 2    |
| 5  | 2    |
+----+------+

SQL Schema for Tree Node

Create table If Not Exists tree (id int, p_id int)
Truncate table tree
insert into tree (id, p_id) values ('1', 'None')
insert into tree (id, p_id) values ('2', '1')
insert into tree (id, p_id) values ('3', '1')
insert into tree (id, p_id) values ('4', '2')
insert into tree (id, p_id) values ('5', '2')

Find out the type of the nodes. Each node has a ID and parent id – if it is a root node, the parent ID will be null. Write a SQL (MySQL) query to print out each node type.

+----+------+
| id | Type |
+----+------+
| 1  | Root |
| 2  | Inner|
| 3  | Leaf |
| 4  | Leaf |
| 5  | Leaf |
+----+------+

For example, the Node 2 is a Inner Type because it’s got Node 4 and 5 as children nodes. And Node 1 is root because its parent id is null.

			  1
			/   \
                      2       3
                    /   \
                  4       5

If a node’s parent id isn’t null, it must be inner or leaf nodes. We can select all p_id from the table, then we have the inner node ID. Using a CASE to choose different values under different circumstances.

1
2
3
4
5

select id, (case
    when p_id is null then "Root"
    when id in (select p_id from tree where p_id is not null) then "Inner"
    else "Leaf"
end) as Type from tree as t1

select id, (case
    when p_id is null then "Root"
    when id in (select p_id from tree where p_id is not null) then "Inner"
    else "Leaf"
end) as Type from tree as t1

Alternatively, we can use the IF() function in MySQL – so the above becomes two nested IF – IF(condition, Then, Else)

1
2
3
4
5

select id, 
    if (p_id is null, "Root",
            if (id in (select p_id from tree where p_id is not null), "Inner", "Leaf")
       ) as Type 
from tree as t1

select id, 
    if (p_id is null, "Root",
            if (id in (select p_id from tree where p_id is not null), "Inner", "Leaf")
       ) as Type 
from tree as t1

There is slightly another way to check if a node is inner type.

1
2
3
4
5

select id, (case
    when p_id is null then "Root"
    when exists (select * from tree as t2 where t1.id = t2.p_id) then "Inner"
    else "Leaf"
end) as Type from tree as t1

select id, (case
    when p_id is null then "Root"
    when exists (select * from tree as t2 where t1.id = t2.p_id) then "Inner"
    else "Leaf"
end) as Type from tree as t1

Rewritten using the IF functions.

1
2
3
4
5

select id, 
    if (p_id is null, "Root", 
      if (exists (select * from tree as t2 where t1.id = t2.p_id), "Inner", "Leaf")
    )
as Type from tree as t1

select id, 
    if (p_id is null, "Root", 
      if (exists (select * from tree as t2 where t1.id = t2.p_id), "Inner", "Leaf")
    )
as Type from tree as t1

The first two methods may be slightly a bit faster since it involves querying the tree table twice – while the last 2 methods join the table.

–EOF (The Ultimate Computing & Technology Blog) —