{x}
blog image

Tree Node

Table: Tree

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| p_id        | int  |
+-------------+------+
id is the column with 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.
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.

 

Example 1:

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:

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: This question is the same as 3054: Binary Tree Nodes.

Solution Explanation and Code

This problem requires determining the type (Root, Inner, Leaf) of each node in a tree represented in a table. The solution leverages SQL's capabilities to efficiently classify nodes based on their parent (p_id) and child relationships.

Approach

The core idea is to check three conditions for each node:

  1. Root: A node is a root if its p_id is NULL.
  2. Inner: A node is an inner node if it's the parent of at least one other node. This is determined by checking if its id exists in the p_id column of the table. A subquery is used for this efficient check.
  3. Leaf: If a node is neither a root nor an inner node, it's a leaf node.

This logic is implemented using SQL's CASE WHEN statement, creating a concise and efficient query.

Time Complexity Analysis

The dominant factor in the time complexity is the subquery id IN (SELECT p_id FROM Tree). In the worst-case scenario, this subquery has to scan the entire Tree table for each row in the outer query. This leads to a nested loop-like behavior, resulting in a time complexity of approximately O(N^2), where N is the number of rows in the Tree table. However, database optimizers might improve this performance significantly in practice, depending on the indexing and the specific database system used. A more optimized approach could use joins, but the given solution prioritizes readability.

Space Complexity Analysis

The space complexity is O(1) because the query uses a constant amount of extra space regardless of the input size. The output table is of the same size as the input table.

Code (MySQL)

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

This MySQL query directly implements the approach described above. The CASE WHEN statement checks the three conditions, assigning the appropriate type to each node. The result is a table with id and type columns, showing the classification of each node in the tree.

Note: While the time complexity analysis suggests O(N^2), database systems often optimize such queries significantly using indexes and query planning, leading to much better performance in practice. For extremely large datasets, exploring alternative approaches using joins or pre-computed information (e.g., storing child counts) might be beneficial.