Teaching Kids Programming – SQL to Determine the Binary Tree Node Types (Left/Right Join – Process Elimination)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Table: Tree

+-------------+------+ 
| Column Name | Type | 
+-------------+------+ 
| N           | int  | 
| P           | int  |
+-------------+------+

N is the column of unique values for this table.
Each row includes N and P, where N represents the value of a node in Binary Tree, and P is the parent of N.
Write a solution to find the node type of the Binary Tree. Output one of the following for each node:

Root: if the node is the root node.
Leaf: if the node is the leaf node.
Inner: if the node is neither root nor leaf node.
Return the result table ordered by node value in ascending order.

The result format is in the following example.

Example 1:

Input:
Tree table:

+---+------+
| N | P    | 
+---+------+
| 1 | 2    |
| 3 | 2    | 
| 6 | 8    | 
| 9 | 8    | 
| 2 | 5    | 
| 8 | 5    | 
| 5 | null | 
+---+------+

Output:

 
+---+-------+
| N | Type  | 
+---+-------+
| 1 | Leaf  | 
| 2 | Inner |
| 3 | Leaf  |
| 5 | Root  |
| 6 | Leaf  |
| 8 | Inner |
| 9 | Leaf  |    
+---+-------+

Explanation:
– Node 5 is the root node since it has no parent node.
– Nodes 1, 3, 6, and 8 are leaf nodes because they don’t have any child nodes.
– Nodes 2, 4, and 7 are inner nodes as they serve as parents to some of the nodes in the structure.

Teaching Kids Programming – SQL to Determine the Binary Tree Node Types (Left/Right Join – Process Elimination)

We apply the process elimination algorithm here (Teaching Kids Programming – SQL to Determine the Binary Tree Node Types (Nested Select – Process Elimination)) to solve this problem.

We also talk about the SQL joins here: Teaching Kids Programming – Introduction to SQL Join Queries (Inner, Left, Right, Full and Cross Joins)

We can then apply the Left Join but we need to inverse the columns otherwise, it would make no sense to join the same table.

select distinct t1.N, 
    case     
    when t1.P is null then 'Root' 
    when t2.P is null then 'Leaf' 
    else 'Inner' end Type 
from Tree t1 
left join Tree t2 
on t1.N = t2.P
order by t1.N asc

We can also apply the Right join – from T1 left join T2 is the same as from T2 right join T1.

select distinct t1.N, 
    case     
    when t1.P is null then 'Root' 
    when t2.P is null then 'Leaf' 
    else 'Inner' end Type 
from Tree t2
right join 
Tree T1
on t1.N = t2.P
order by T1.N asc

An alternative would be to inverse the columns:

select distinct t2.N, 
    case     
    when t2.P is null then 'Root' 
    when t1.P is null then 'Leaf' 
    else 'Inner' end Type 
from Tree t1 
right join 
Tree T2 
on t1.P = t2.N
order by T2.N asc

–EOF (The Ultimate Computing & Technology Blog) —