SQL MOSAIC #608. Tree Node
Date: 6.26.22
608. Tree Node
Each node in the tree can be one of three types:
- “Leaf”: if the node is a leaf node.
- “Root”: if the node is the root of the tree.
- “Inner”: If the node is neither a leaf node nor a root node.
Write an SQL query to report the type of each node in the tree.
Return the result table ordered by id in ascending order.
Thinking Pathways
“Leaf”: 3, 4, 5
“Root”: 1
“Inner”: 2, 3
- My first thought is to use CASE WHEN to define Leaf, Root, Inner (INCORRECT) e.g.
CASE WHEN p_id = 1 THEN type = “Inner”
CASE WHEN p_id = 2 THEN type = “Leaf”
This does not apply to all. For example, 3 has p_id 1, but it’s not a Inner, it’s a Leaf.
- Steps:
- #Define “Root”
SELECT id, ‘Root’ AS Type
FROM tree
WHERE p_id IS NULL
2. Define “Leaf”
SELECT id, “Leaf” AS Type
FROM tree
WHERE id NOT IN (
SELECT DISTINCT p_id
FROM tree
WHERE p_id IS NOT NULL) AND p_id IS NOT NULL
3. Define “Inner”
SELECT id, “Inner” AS Type
FROM tree
WHERE id IN (
SELECT DISTINCT p_id
FROM tree
WHERE p_id IS NOT NULL)
AND p_id IS NOT NULL
4. UNION
Solution(s):
Solution1: UNION
SELECT id, ‘Root’ AS type
FROM Tree
WHERE p_id IS NULL
UNION
SELECT id, “Leaf” AS Type
FROM tree
WHERE id NOT IN (
SELECT DISTINCT p_id
FROM tree
WHERE p_id IS NOT NULL)
AND p_id IS NOT NULL
UNION
SELECT id, “Inner” AS Type
FROM tree
WHERE id IN (
SELECT DISTINCT p_id
FROM tree
WHERE p_id IS NOT NULL)
AND p_id IS NOT NULL
Solution2: CASE WHEN
SELECT id,
CASE
WHEN p_id IS NULL THEN “Root”
WHEN id IN (SELECT DISTINCT p_id
FROM Tree) THEN “Inner”
Else ‘Leaf’
END AS type
FROM Tree
ORDER BY ‘id’
