Domain 2MediumCORE

Tree Node

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).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 0

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:

  1. Root: A node with no parent (p_id IS NULL).
  2. Leaf: A node that has a parent but does not have any children (its id never appears as a p_id in another row).
  3. 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_id can 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:

  1. Check if its parent is NULL -> Root.
  2. 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 id appears as a value in any other row’s p_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_id collection, it means someone else uses this node as a parent. So yes, Inner.

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

  1. Data Preparation: Iterate through the input tree data once. Store every non-null parent ID (p_id) into a set called has_children. This represents all nodes that have at least one child (i.e., their ID appears as a p_id). Note: We collect values from column index 1, not column index 0.
  2. Classification Loop: Iterate through each row in the original table again (or maintain state). For each node:
    • If its p_id is NULL, assign type ‘Root’.
    • Else if its id is NOT present in our “has_children” set, it has no children -> assign ‘Leaf’.
    • Otherwise (p_id exists AND id appears as a child), assign ‘Inner’.
  3. 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_id values 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_data handles 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 in has_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 None to distinguish Root from others, ensuring no type errors on null values in Python.