Binary Tree Nodes - Problem
Given a table Tree representing a binary tree structure, write a SQL query to classify each node as one of the following types:
- Root: The node that has no parent (P is NULL)
- Leaf: The node that has no children (not referenced as a parent by any other node)
- Inner: The node that has both a parent and at least one child
Return the result table with columns N (node value) and Type (node classification), ordered by node value in ascending order.
Table Schema
Tree
| Column Name | Type | Description |
|---|---|---|
N
PK
|
int | Node value (unique identifier) |
P
|
int | Parent node value (NULL for root node) |
Primary Key: N
Note: Each row represents a node in the binary tree with its parent reference
Input & Output
Example 1 — Simple Binary Tree
Input Table:
| N | P |
|---|---|
| 1 | 2 |
| 2 | |
| 3 | 2 |
Output:
| N | Type |
|---|---|
| 1 | Leaf |
| 2 | Root |
| 3 | Leaf |
💡 Note:
Node 2 is the root (P is NULL). Nodes 1 and 3 are children of node 2 with no children themselves, making them leaf nodes.
Example 2 — Tree with Inner Node
Input Table:
| N | P |
|---|---|
| 1 | 2 |
| 2 | 5 |
| 3 | 2 |
| 4 | 5 |
| 5 |
Output:
| N | Type |
|---|---|
| 1 | Leaf |
| 2 | Inner |
| 3 | Leaf |
| 4 | Leaf |
| 5 | Inner |
💡 Note:
Node 5 is the root. Node 2 is an inner node (has parent 5 and children 1,3). Node 5 is also inner (root with children). Nodes 1, 3, and 4 are leaves.
Example 3 — Single Node Tree
Input Table:
| N | P |
|---|---|
| 1 |
Output:
| N | Type |
|---|---|
| 1 | Root |
💡 Note:
Single node with no parent becomes the root node, even though it has no children.
Constraints
-
1 ≤ N ≤ 1000 -
PisNULLfor root nodes -
Each node value
Nis unique - Valid binary tree structure guaranteed
Visualization
Tap to expand
Understanding the Visualization
1
Input Tree
Parent-child relationships
2
Classification
Check parent/child status
3
Node Types
Root, Inner, or Leaf
Key Takeaway
🎯 Key Insight: Node classification depends on parent existence (P IS NULL) and child existence (appearing as parent in other rows)
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code