608 Tree Node

Description

Table: Tree

• id is the primary key column for this table.
• Each row of this table contains information about the id of a node and the id of its parent node in a tree.
• The given structure is always a valid tree.
• 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.

Problem Statement

Write a SQL query to report the type of each node in the tree.

Return the result table ordered by id in ascending order. The query result format is in the following example.

Example 1:

Input:

• Tree table:

Output:

Explanation:

• Node 1 is the root node because its parent node is null and it has child nodes 2 and 3.
• Node 2 is an inner node because it has parent node 1 and child node 4 and 5.
• Nodes 3, 4, and 5 are leaf nodes because they have parent nodes and they do not have child nodes.

Example 2:

Input:

• Tree table:

Output:

Explanation:

• If there is only one node on the tree, you only need to output its root attributes.

Solution

The problem asks you to identify the type of each node based on its parent and child nodes. You can assign the type using following logic.

• If the current node has p_id as NULL, it is a Root node.
• If the current node’s p_id is present as id in the table, it is an Inner node.
• Otherwise, it is a Leaf node.

To apply this logic, you can use CASE WHEN statement in SQL.

1SELECT id, 
2    CASe 
3        WHEN p_id IS NULL THEN 'Root'
4        WHEN id IN (SELECT p_id FROM Tree) THEN 'Inner'
5        ELSE 'Leaf'
6    END AS type
7FROM Tree;