## 608. Tree Node

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

```+----+------+
| 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:

```+----+------+
| 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
```

Note

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

b'
\n\n

## Solution

\n
\n

#### Approach I: Using `UNION` [Accepted]

\n

Intuition

\n

We can print the node type by judging every record by its definition in this table.\n Root: it does not have a parent node at all\n Inner: it is the parent node of some nodes, and it has a not NULL parent itself.\n* Leaf: rest of the cases other than above two

\n

Algorithm

\n

By transiting the node type definition, we can have the following code.

\n

For the root node, it does not have a parent.

\n
`SELECT\n    id, \'Root\' AS Type\nFROM\n    tree\nWHERE\n    p_id IS NULL\n`
\n

For the leaf nodes, they do not have any children, and it has a parent.

\n
`SELECT\n    id, \'Leaf\' AS Type\nFROM\n    tree\nWHERE\n    id NOT IN (SELECT DISTINCT\n            p_id\n        FROM\n            tree\n        WHERE\n            p_id IS NOT NULL)\n        AND p_id IS NOT NULL\n`
\n

For the inner nodes, they have have some children and a parent.

\n
`SELECT\n    id, \'Inner\' AS Type\nFROM\n    tree\nWHERE\n    id IN (SELECT DISTINCT\n            p_id\n        FROM\n            tree\n        WHERE\n            p_id IS NOT NULL)\n        AND p_id IS NOT NULL\n`
\n

So, one solution to the problem is to combine these cases together using `UNION`.

\n

MySQL

\n
`SELECT\n    id, \'Root\' AS Type\nFROM\n    tree\nWHERE\n    p_id IS NULL\n\nUNION\n\nSELECT\n    id, \'Leaf\' AS Type\nFROM\n    tree\nWHERE\n    id NOT IN (SELECT DISTINCT\n            p_id\n        FROM\n            tree\n        WHERE\n            p_id IS NOT NULL)\n        AND p_id IS NOT NULL\n\nUNION\n\nSELECT\n    id, \'Inner\' AS Type\nFROM\n    tree\nWHERE\n    id IN (SELECT DISTINCT\n            p_id\n        FROM\n            tree\n        WHERE\n            p_id IS NOT NULL)\n        AND p_id IS NOT NULL\nORDER BY id;\n`
\n

#### Approach II: Using flow control statement `CASE` [Accepted]

\n

Algorithm

\n

The idea is similar with the above solution but the code is simpler by utilizing the flow control statements, which is effective to output differently based on different input values. In this case, we can use `CASE` statement.

\n

MySQL

\n
`SELECT\n    id AS `Id`,\n    CASE\n        WHEN tree.id = (SELECT atree.id FROM tree atree WHERE atree.p_id IS NULL)\n          THEN \'Root\'\n        WHEN tree.id IN (SELECT atree.p_id FROM tree atree)\n          THEN \'Inner\'\n        ELSE \'Leaf\'\n    END AS Type\nFROM\n    tree\nORDER BY `Id`\n;\n`
\n
\n

MySQL provides different flow control statements besides `CASE`. You can try to rewrite the slution above using `IF` flow control statement.

\n
\n

#### Approach III: Using `IF` function [Accepted]

\n

Algorithm

\n

Also, we can use a single `IF` function instead of the complex flow control statements.

\n

MySQL

\n
`SELECT\n    atree.id,\n    IF(ISNULL(atree.p_id),\n        \'Root\',\n        IF(atree.id IN (SELECT p_id FROM tree), \'Inner\',\'Leaf\')) Type\nFROM\n \xc2\xa0 \xc2\xa0tree atree\nORDER BY atree.id\n`
\n
\n

Note: This solution was inspired by @richarddia

\n
\n
'