Teaching Kids Programming – SQL to Determine the Binary Tree Node Types (Nested Select – 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.

SQL to Determine the Binary Tree Node Types (Nested Select – Process Elimination Algorithm)

We can apply Process Elimination algorithm to determine the type for the nodes in the given binary tree. If the parent is Null (only single node), then it is the single Root. Otherwise, we check if it is some other nodes’ parents, if yes, then it is a inner node otherwise, it must be a leaf node.

The SQL provides the IF function which is in the form of IF(Expression, ValueWhenTrue, ValueWhenFalse). We can nested the if checks, also we need a subquery to return the parent nodes of the same tree.

select 
    N, 
    if(P is null, 
        "Root", 
        if(N in (select distinct P from Tree), "Inner", "Leaf")) as Type
from Tree
order by N

This isn’t clean – and a bit messy, we can use the SQL case keyword which is a syntax sugar to make it cleaner/neat.

select
N, 
case when P is null then "Root"
     when N in (select distinct P from Tree) then "Inner"
     else "Leaf"
     end as Type
from Tree
order by N

We can also solve this by left/right joining the same tree table. We will talk about this soon.

–EOF (The Ultimate Computing & Technology Blog) —