sql notes: leetcode#608 tree node

Problem

Given a table tree, id is identifier of the tree node and p_id is its parent node’s id.

1
2
3
4
5
6
7
8
9

+----+------+
| id | p_id |
+----+------+
| 1  | null |
| 2  | 1    |
| 3  | 1    |
| 4  | 2    |
| 5  | 2    |
+----+------+

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 a query to print the node id and the type of the node. Sort your output by the node id. The result for the above sample is:

1
2
3
4
5
6
7
8
9

+----+------+
| id | Type |
+----+------+
| 1  | Root |
| 2  | Inner|
| 3  | Leaf |
| 4  | Leaf |
| 5  | Leaf |
+----+------+

Explanation

• Node ‘1’ is root node, because its parent node is NULL and it has child node ‘2’ and ‘3’.
• Node ‘2’ is inner node, because it has parent node ‘1’ and child node ‘4’ and ‘5’.
• Node ‘3’, ‘4’ and ‘5’ is Leaf node, because they have parent node and they don’t have child node.

And here is the image of the sample tree as below:

1
2
3
4
5

        1
      /   
    2       3
  /   
4       5

Note

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

Analysis

Given a node, we can check if it is a root first, if not, check whether it is inner or leaf.

A node is root if its parent id is null:

1
2

SELECT id, IF(ISNULL(p_id), 'Root', IF()) AS Type 
FROM tree;

For a non-root node, if it is parent node of some other nodes, it should be inner, otherwise leaf:

1
2

SELECT id, IF(ISNULL(p_id), 'Root', IF(id IN (SELECT p_id FROM tree), 'Inner', 'Leaf')) AS Type 
FROM tree;

At last, sort result by id:

1
2

SELECT id, IF(ISNULL(p_id), 'Root', IF(id IN (SELECT p_id FROM tree), 'Inner', 'Leaf')) AS Type 
FROM tree ORDER BY id;

Solution

1
2

SELECT id, IF(ISNULL(p_id), 'Root', IF(id IN (SELECT p_id FROM tree), 'Inner', 'Leaf')) AS Type 
FROM tree ORDER BY id;

Link

608. Tree Node
(中文版) SQL 笔记: Leetcode#608 Tree Node