Question

3054. Binary Tree Nodes

中文文档

Description

Table: Tree

+-------------+------+ 
| Column Name | Type | 
+-------------+------+ 
| N       | int  | 
| P       | int  |
+-------------+------+
N is the column of unique values for this table.
Each row includes N and P, where N represents the value of a node in Binary Tree, and P is the parent of N.

Write a solution to find the node type of the Binary Tree. Output one of the following for each node:

• Root: if the node is the root node.
• Leaf: if the node is the leaf node.
• Inner: if the node is neither root nor leaf node.

Return _the result table ordered by node value in ascending order_.

The result format is in the following example.

 

Example 1:

Input: 
Tree table:
+---+------+
| N | P  | 
+---+------+
| 1 | 2  |
| 3 | 2  | 
| 6 | 8  | 
| 9 | 8  | 
| 2 | 5  | 
| 8 | 5  | 
| 5 | null | 
+---+------+
Output: 
+---+-------+
| N | Type  | 
+---+-------+
| 1 | Leaf  | 
| 2 | Inner |
| 3 | Leaf  |
| 5 | Root  |
| 6 | Leaf  |
| 8 | Inner |
| 9 | Leaf  |  
+---+-------+
Explanation: 
- Node 5 is the root node since it has no parent node.
- Nodes 1, 3, 6, and 8 are leaf nodes because they don't have any child nodes.
- Nodes 2, 4, and 7 are inner nodes as they serve as parents to some of the nodes in the structure.

Solutions

Solution 1: Left Join

If a node's parent is null, then it is a root node; if a node is not the parent of any node, then it is a leaf node; otherwise, it is an internal node.

Therefore, we use left join to join the Tree table twice, with the join condition being t1.N = t2.P. If t1.P is null, then t1.N is a root node; if t2.P is null, then t1.N is a leaf node; otherwise, t1.N is an internal node.

# Write your MySQL query statement below
SELECT DISTINCT
  t1.N AS N,
  IF(t1.P IS NULL, 'Root', IF(t2.P IS NULL, 'Leaf', 'Inner')) AS Type
FROM
  Tree AS t1
  LEFT JOIN Tree AS t2 ON t1.N = t2.p
ORDER BY 1;