Binary Hierarchy Node Role Tagging

EASY10 pts

A platform stores a rooted binary hierarchy in the table Tree.

Schema:

N: unique integer id of a node
P: integer id of the parent node (NULL means this node is the root)

Every row is one node in the same valid tree.

Your task is to label each node with exactly one category:

Root: node has no parent (P is NULL)
Inner: node is not Root and appears as a parent of at least one other node
Leaf: node is not Root and has no children

Return the result with exactly two columns:

N
Type

Sort by N in ascending order.

Supported submission environments:

SQL (SQLite 3.27.2)
Pandas (Python)

Example

Input

Tree:
| N | P    |
|---|------|
| 1 | 2    |
| 3 | 2    |
| 6 | 8    |
| 9 | 8    |
| 2 | 5    |
| 8 | 5    |
| 5 | null |

Output

[
  {"N":1,"Type":"Leaf"},
  {"N":2,"Type":"Inner"},
  {"N":3,"Type":"Leaf"},
  {"N":5,"Type":"Root"},
  {"N":6,"Type":"Leaf"},
  {"N":8,"Type":"Inner"},
  {"N":9,"Type":"Leaf"}
]

Explanation

Node 5 is the only root. Nodes 2 and 8 each have at least one child, so they are Inner. Nodes 1, 3, 6, and 9 have no children, so they are Leaf.

Example

Input

Tree:
| N  | P    |
|----|------|
| 42 | null |

Output

[
  {"N":42,"Type":"Root"}
]

Explanation

A one-node tree contains only the root.

Example

Input

Tree:
| N  | P    |
|----|------|
| 50 | 20   |
| 70 | 50   |
| 10 | null |
| 20 | 10   |
| 30 | 10   |
| 40 | 20   |

Output

[
  {"N":10,"Type":"Root"},
  {"N":20,"Type":"Inner"},
  {"N":30,"Type":"Leaf"},
  {"N":40,"Type":"Leaf"},
  {"N":50,"Type":"Inner"},
  {"N":70,"Type":"Leaf"}
]

Explanation

Node 10 has no parent and is Root. Nodes 20 and 50 each appear as parents, so they are Inner. Nodes 30, 40, and 70 are non-root nodes with no children, so they are Leaf.

Accepted0/0·0% Acceptance

Constraints

1 <= number of rows in Tree <= 100000
1 <= N <= 2000000000
N is unique in each test case
Exactly one node has P = NULL
Every non-null P references an existing N
Input always forms one valid rooted tree with no cycles
Return exactly columns N and Type
Type values must be Root, Inner, or Leaf
Sort output by N ascending
SQL submissions run on SQLite 3.27.2
Pandas submissions must return a DataFrame

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

Tree =

[{"N":42,"P":null}]

Binary Hierarchy Node Role Tagging

Hints

Binary Hierarchy Node Role Tagging

Hints