Formatted question description: https://leetcode.ca/all/608.html
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 | +----+------+
- 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
If there is only one node on the tree, you only need to output its root attributes.
Select the three types of node individually. Then use union to merge the result, and sort the result according to
A node is a leaf if and only if it is not any node’s parent and it has a parent.
A node is a root if and only if it does not have a parent. In other words,
A node is an inner node if and only if it is one or more nodes’ parent and it has a parent.
Therefore, to determine a
Root, simply use
p_id. To determine a
Inner, check the current entry’s
p_id and whether the current entry’s
id is in some entry’s
# Write your MySQL query statement below 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 order by id;