00:00:00

Description

Editorial

Hierarchy Node Role Classification

EASY10 pts

You are given a table named tree that describes a rooted hierarchy.

Columns:

id: unique identifier of a node
p_id: parent node id (null means this node is the root)

The dataset always forms one valid tree:

exactly one root node,
each non-root node has exactly one parent,
no cycles are present.

Classify every node into one of three labels:

Root: the node has p_id = null
Inner: the node is not root and has at least one child
Leaf: the node is not root and has no children

Return exactly two columns:

id
type

Rows may be returned in any order.

Supported submission environments:

SQL (SQLite 3.27.2)
Pandas (Python)

Example

Input

tree:
| id | p_id |
|----|------|
| 1  | null |
| 2  | 1    |
| 3  | 1    |
| 4  | 2    |
| 5  | 2    |

Output

[
  {"id":1,"type":"Root"},
  {"id":2,"type":"Inner"},
  {"id":3,"type":"Leaf"},
  {"id":4,"type":"Leaf"},
  {"id":5,"type":"Leaf"}
]

Explanation

Node 1 has no parent, so it is Root. Node 2 has both a parent and children, so it is Inner. Nodes 3, 4, and 5 have no children, so they are Leaf.

Example

Input

tree:
| id | p_id |
|----|------|
| 10 | null |

Output

[
  {"id":10,"type":"Root"}
]

Explanation

A single-node tree has only one node, and it must be Root.

Example

Input

tree:
| id  | p_id |
|-----|------|
| 90  | 30   |
| 20  | 10   |
| 10  | null |
| 30  | 10   |
| 40  | 20   |
| 50  | 20   |
| 60  | 50   |

Output

[
  {"id":10,"type":"Root"},
  {"id":20,"type":"Inner"},
  {"id":30,"type":"Inner"},
  {"id":40,"type":"Leaf"},
  {"id":50,"type":"Inner"},
  {"id":60,"type":"Leaf"},
  {"id":90,"type":"Leaf"}
]

Explanation

Node 10 is Root. Nodes 20, 30, and 50 each have children, so they are Inner. Remaining non-root nodes without children are Leaf.

Accepted0/0·0% Acceptance

Constraints

1 <= number of rows in tree <= 100000
1 <= id <= 2000000000
id is unique
p_id is null for exactly one node
For non-root nodes, p_id references an existing id
The input always represents one valid rooted tree (no cycles)
Use SQLite 3.27.2 semantics for SQL submissions
For Pandas submissions, return exactly two columns: id and type

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

tree =

[{"id":90,"p_id":30},{"id":40,"p_id":20},{"id":10,"p_id":null},{"id":30,"p_id":10},{"id":60,"p_id":50},{"id":50,"p_id":20},{"id":20,"p_id":10}]

Loading problem...

101

00:00:00

Description

Editorial

Hierarchy Node Role Classification

EASY10 pts

You are given a table named tree that describes a rooted hierarchy.

Columns:

id: unique identifier of a node
p_id: parent node id (null means this node is the root)

The dataset always forms one valid tree:

exactly one root node,
each non-root node has exactly one parent,
no cycles are present.

Classify every node into one of three labels:

Root: the node has p_id = null
Inner: the node is not root and has at least one child
Leaf: the node is not root and has no children

Return exactly two columns:

id
type

Rows may be returned in any order.

Supported submission environments:

SQL (SQLite 3.27.2)
Pandas (Python)

Example

Input

tree:
| id | p_id |
|----|------|
| 1  | null |
| 2  | 1    |
| 3  | 1    |
| 4  | 2    |
| 5  | 2    |

Output

[
  {"id":1,"type":"Root"},
  {"id":2,"type":"Inner"},
  {"id":3,"type":"Leaf"},
  {"id":4,"type":"Leaf"},
  {"id":5,"type":"Leaf"}
]

Explanation

Node 1 has no parent, so it is Root. Node 2 has both a parent and children, so it is Inner. Nodes 3, 4, and 5 have no children, so they are Leaf.

Example

Input

tree:
| id | p_id |
|----|------|
| 10 | null |

Output

[
  {"id":10,"type":"Root"}
]

Explanation

A single-node tree has only one node, and it must be Root.

Example

Input

tree:
| id  | p_id |
|-----|------|
| 90  | 30   |
| 20  | 10   |
| 10  | null |
| 30  | 10   |
| 40  | 20   |
| 50  | 20   |
| 60  | 50   |

Output

[
  {"id":10,"type":"Root"},
  {"id":20,"type":"Inner"},
  {"id":30,"type":"Inner"},
  {"id":40,"type":"Leaf"},
  {"id":50,"type":"Inner"},
  {"id":60,"type":"Leaf"},
  {"id":90,"type":"Leaf"}
]

Explanation

Node 10 is Root. Nodes 20, 30, and 50 each have children, so they are Inner. Remaining non-root nodes without children are Leaf.

Accepted0/0·0% Acceptance

Constraints

1 <= number of rows in tree <= 100000
1 <= id <= 2000000000
id is unique
p_id is null for exactly one node
For non-root nodes, p_id references an existing id
The input always represents one valid rooted tree (no cycles)
Use SQLite 3.27.2 semantics for SQL submissions
For Pandas submissions, return exactly two columns: id and type

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

tree =

[{"id":90,"p_id":30},{"id":40,"p_id":20},{"id":10,"p_id":null},{"id":30,"p_id":10},{"id":60,"p_id":50},{"id":50,"p_id":20},{"id":20,"p_id":10}]

Hierarchy Node Role Classification

Hints

Hierarchy Node Role Classification

Hints