forked from fishercoder1534/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path_608.sql
More file actions
55 lines (54 loc) · 1.69 KB
/
_608.sql
File metadata and controls
55 lines (54 loc) · 1.69 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
--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.
--credit: https://leetcode.com/articles/tree-node/#approach-i-using-union-accepted
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;