# SQL self-join to label nodes on binary search tree

Would like feedback on my SQL (1) efficiency and (2) readability, and if the conditions I featured in my CASE statement could be transferred to a join, etc.

Here's the problem I'm solving:

Say you have a table bst with a column of nodes and column or corresponding parent nodes:

node   Parent
1       2
2       5
3       5
4       3
5       NULL


We want to write SQL such that we label each node as a “leaf”, “inner” or “Root” node, such that for the nodes above we get:

Node    Label
1       Leaf
2       Inner
3       Inner
4       Leaf
5       Root


Here's my solution:

WITH join_table AS
(
SELECT
a.node a_node,
a.parent a_parent,
b.node b_node,
b.parent b_parent
FROM
bst a
LEFT JOIN
bst b ON a.parent = b.node
)

SELECT
a_node as Node,
CASE
WHEN b_node IS NOT NULL and b_parent IS NOT NULL THEN 'Leaf'
WHEN b_node IS NOT NULL and b_parent IS NULL THEN 'Inner'
WHEN b_node IS NULL and b_parent IS NULL THEN 'Root'
ELSE 'Error'
END AS Label
FROM
join_table

• What dialect of SQL are you targeting? (Apart from that, this is a really well-asked SQL question, so well done!) – Toby Speight Jan 30 '19 at 16:58
• @TobySpeight Let's just say Hive, but Postgres or MySQL would work too -- more focused on the underlying logic – zthomas.nc Jan 30 '19 at 17:14
• It is possible to rewrite your query without CASE, however, it will not help the performance since you are reading the whole tables anyway. The sequential scan is inevitable in this case. – Radim Bača Jan 30 '19 at 19:17
• @RadimBača Feel free to post such a response – zthomas.nc Jan 31 '19 at 16:17
• @zthomas.nc it would be a solution using UNION ALL which would lead to three sequential scans instead of one. – Radim Bača Jan 31 '19 at 18:19