Problem

Table: Tree

1
2
3
4
5
6
7
8

+-------------+------+ 
| Column Name | Type | 
+-------------+------+ 
| id          | int  | 
| p_id           | int  |
+-------------+------+
id is the column of unique values for this table.
Each row of this table contains information about the id of a node and the id of its parent node in a tree.

In leetcode 3054, table is specified as:

1
2
3
4
5
6
7
8

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

The given structure is always a valid tree.

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 solution to report the type of each node in the tree.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1

 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




Input: 
Tree table:
+----+------+
| id | p_id |
+----+------+
| 1  | null |
| 2  | 1    |
| 3  | 1    |
| 4  | 2    |
| 5  | 2    |
+----+------+
Output: 
+----+-------+
| id | type  |
+----+-------+
| 1  | Root  |
| 2  | Inner |
| 3  | Leaf  |
| 4  | Leaf  |
| 5  | Leaf  |
+----+-------+
Explanation: 
Node 1 is the root node because its parent node is null and it has child nodes 2 and 3.
Node 2 is an inner node because it has parent node 1 and child node 4 and 5.
Nodes 3, 4, and 5 are leaf nodes because they have parent nodes and they do not have child nodes.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Input: 
Tree table:
+----+------+
| id | p_id |
+----+------+
| 1  | null |
+----+------+
Output: 
+----+-------+
| id | type  |
+----+-------+
| 1  | Root  |
+----+-------+
Explanation: If there is only one node on the tree, you only need to output its root attributes.

Note

Note: The questions 608: Tree Node. and 3054: Binary Tree Nodes. are same.

Solution

Method 1 – SQL Set Operations

Intuition

A root node has no parent (P is null). A leaf node is not a parent of any node (its N does not appear as a P). An inner node is neither root nor leaf.

Approach

  • Use SQL to classify each node:
    • If p_id (P) is null, it’s a root.
    • If id(N) is not in any p_id(P), it’s a leaf.
    • Otherwise, it’s an inner node.

Code

1
2
3
4
5
6
7

SELECT id,
  CASE
    WHEN p_id IS NULL THEN 'Root'
    WHEN id NOT IN (SELECT DISTINCT p_id FROM Tree WHERE p_id IS NOT NULL) THEN 'Leaf'
    ELSE 'Inner'
  END AS type
FROM Tree;
1
2
3
4
5
6
7

SELECT id,
  CASE
    WHEN p_id IS NULL THEN 'Root'
    WHEN id NOT IN (SELECT DISTINCT p_id FROM Tree WHERE p_id IS NOT NULL) THEN 'Leaf'
    ELSE 'Inner'
  END AS type
FROM Tree;
1
2
3
4
5
6
7

SELECT id,
  CASE
    WHEN p_id IS NULL THEN 'Root'
    WHEN id NOT IN (SELECT DISTINCT p_id FROM Tree WHERE p_id IS NOT NULL) THEN 'Leaf'
    ELSE 'Inner'
  END AS type
FROM Tree;

Explanation

We classify each node as follows:

  • Root: The node whose p_id is NULL (no parent).
  • Leaf: The node whose id does not appear as any other node’s p_id (i.e., is not a parent of any node).
  • Inner: Any node that is neither root nor leaf (has a parent and is also a parent).

The query uses a CASE statement to assign the type for each node. The subquery (SELECT p_id FROM Tree WHERE p_id IS NOT NULL) collects all parent ids, so if a node’s id is not in this set, it is a leaf.

Complexity Analysis

  • ⏰ Time complexity: O(n^2) (due to the subquery for each row; can be improved with joins or CTEs)
  • 🧺 Space complexity: O(n) (for the subquery result set)

Complexity

  • ⏰ Time complexity: O(n^2) (due to subquery, but can be improved with joins)
  • 🧺 Space complexity: O(n)