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:
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 9 are leaf nodes because they don't have any child nodes. - Nodes 2, and 8 are inner nodes as they serve as parents to some of the nodes in the structure.
Note: This question is the same as 608: Tree Node.
Problem Overview: Given a table representing a tree, each row stores a node and its parent. Your task is to classify every node as Root, Inner, or Leaf. A node is Root if it has no parent, Inner if it has at least one child, and Leaf if it has no children.
Approach 1: Self Left Join (O(n) time, O(1) extra space)
This problem is naturally solved with a self join. Treat the table as two logical copies: one representing the current node and the other representing potential child nodes. Perform a LEFT JOIN where the parent node's id matches the child's parent_id. If a row from the second table exists, the node has at least one child.
Use a CASE expression to classify nodes. If parent_id IS NULL, the node is the Root. If the join finds a matching child row, the node is an Inner node. Otherwise, it has no children and must be a Leaf. Because joins may produce duplicate rows for nodes with multiple children, apply GROUP BY on the node id to keep one result per node.
This approach works because a self join allows you to check parent-child relationships directly within the same table. The database scans the table once and resolves relationships through the join, resulting in roughly O(n) time depending on indexing. Extra memory usage is constant since classification happens during query execution.
SQL tree problems often rely on the same idea: compare rows within the same table using joins. Understanding SQL joins, especially self joins, is essential when working with hierarchical data stored in relational database tables.
Recommended for interviews: The self LEFT JOIN approach is the expected solution. It demonstrates that you understand hierarchical relationships in relational tables and know how to detect child rows using joins. Simpler conditional checks identify the root node, while the join determines whether the node is inner or leaf.
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.
MySQL
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Self Left Join | O(n) | O(1) | Best general solution for identifying parent-child relationships directly in SQL |
| Self Join + Aggregation | O(n) | O(1) | Useful when counting children explicitly or when duplicates from joins must be aggregated |
Leetcode MEDIUM 3054 - Binary Tree Nodes CASE WHEN DSA SQL - Explained by Everyday Data Science • Everyday Data Science • 478 views views
Practice Binary Tree Nodes with our built-in code editor and test cases.
Practice on FleetCode