Binary Hierarchy Node Role Tagging

Easy

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 1

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 2

Input

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

Output

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

Explanation

A one-node tree contains only the root.

Example 3

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.

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

Loading problem...

Preparing your editor. You can read the problem while it loads.

Binary Hierarchy Node Role Tagging

Easy

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 1

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 2

Input

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

Output

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

Explanation

A one-node tree contains only the root.

Example 3

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.

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