608. Tree Node
Model: qwen3.5:9b
Topics:
FAANG asked: 0
Acceptance rate: 69.9%
Problem Breakdown
We need to classify nodes in a tree structure based on their relationships within the provided schema (tree). The input consists of two columns: id (unique identifier) and p_id (parent ID).
Key Logic:
- Root: A node with no parent (
p_id IS NULL). - Leaf: A node that has a parent but does not have any children (its
idnever appears as ap_idin another row). - Inner: Any other node (has a parent and at least one child).
Constraints & Edge Cases:
- The input table represents a valid tree structure, so there are no cycles or duplicate IDs for the same level of hierarchy logic issues beyond standard SQL constraints.
p_idcan be NULL only once per row if it’s a root node (though typically one root exists).- We must handle cases where a node is neither Root nor Leaf correctly by checking existence in child sets efficiently.
Intuition
If I were explaining this out loud, my first thought would be to iterate through every pair of nodes to check relationships. That’s O(N^2) and definitely too slow for large datasets (Time Limit Exceeded).
I need a way to quickly determine if an id has children without scanning the whole table repeatedly. The key insight is that “having children” means this specific node ID appears in the p_id column of some other row.
So, I can pre-calculate which IDs are parents by collecting all non-NULL values from the p_id column into a Set (O(N) time). Then for every single row:
- Check if its parent is NULL -> Root.
- If it has a parent, check if that ID exists in my “Parents” set? No wait.
- Wait, logic correction needed here. We need to know if the current node’s
idappears as a value in any other row’sp_id. - So we collect all non-NULL values from column 2 (
row[1]) into our set. This represents IDs that have children. - No? It means it has no children -> assign ‘Leaf’.
- Yes (ID exists in parent-set)? Wait, if ID is in the
p_idcollection, it means someone else uses this node as a parent. So yes, Inner.
- Wait, logic correction needed here. We need to know if the current node’s
This reduces the complexity to O(N) because Set lookups are constant time on average. This is much more scalable than nested loops or self-joins in SQL logic when implementing algorithmically.
Approach
- Data Preparation: Iterate through the input
treedata once. Store every non-null parent ID (p_id) into a set calledhas_children. This represents all nodes that have at least one child (i.e., their ID appears as ap_id). Note: We collect values from column index 1, not column index 0. - Classification Loop: Iterate through each row in the original table again (or maintain state). For each node:
- If its
p_idis NULL, assign type ‘Root’. - Else if its
idis NOT present in our “has_children” set, it has no children -> assign ‘Leaf’. - Otherwise (
p_idexists ANDidappears as a child), assign ‘Inner’.
- If its
- Output: Construct the result list with columns
(id, type).
Complexity Analysis
- Time Complexity: O(N). We iterate through the table twice (once to build the set of parents/children, once to classify nodes). Set insertion and lookup are amortized O(1), so total time is linear relative to N rows.
- Space Complexity: O(N). We store all unique
p_idvalues in a hash set (has_children) which takes space proportional to the number of non-root nodes (nodes that have children).
Solution
from typing import List, Tuple, Optional
def tree_node_types(tree_data: List[Tuple[int, Optional[int]]]) -> List[Tuple[int, str]]:
"""
Classifies each node in a tree as 'Root', 'Leaf', or 'Inner'.
Args:
tree_data: A list of tuples (id, p_id) representing the table rows.
id is int, p_id is Optional[int] (None if root).
Returns:
List of tuples (id, type).
"""
# 1. Identify all IDs that have children by collecting non-null parents into a set.
# We collect row[1] because we want to know which node IDs appear as p_id in other rows.
has_children = {row[1] for row in tree_data if row[1] is not None}
result = []
# 2. Iterate through each node to determine its type based on parent/child status
for id_val, p_id in tree_data:
if p_id is None:
# No parent exists -> Root
res_type = 'Root'
elif id_val not in has_children:
# Has a parent but no children (id never appears as a child) -> Leaf
res_type = 'Leaf'
else:
# Has a parent and at least one child -> Inner
res_type = 'Inner'
result.append((id_val, res_type))
return result
# Example usage matching the schema logic (simulating SQL output)
if __name__ == "__main__":
sample_tree = [
(1, None), # Root
(2, 1), # Child of 1
(3, 2), # Leaf child of 2
(4, 2), # Inner node?
# Node 1: p_id=None -> Root
# Node 2: p_id=1. Is '2' in has_children? Yes if there is a row with p_id=2.
# If we have (3,2) and (4,2), then '2' is in children_set. So node 2 is Inner.
]
print(tree_node_types(sample_tree))
Edge Cases Handled
- Empty Input: The loop over
tree_datahandles an empty list gracefully returning an empty result. - Single Node Tree: If only
(1, None)exists, it correctly identifies as ‘Root’. It won’t be inhas_children, so no false positives for Leaf/Inner occur. - Deep Trees / Wide Branches: The set-based approach handles arbitrary depth and branching factor without performance degradation (unlike recursive SQL or nested loops).
- NULL Handling: Explicitly checks
p_id is Noneto distinguish Root from others, ensuring no type errors on null values in Python.