LeetCode 608: Tree Node Solution in Python – A Step-by-Step Guide

What Is LeetCode 608: Tree Node?

In LeetCode 608: Tree Node, you’re given a table tree with two columns: id (node identifier) and p_id (parent identifier, null for the root). Your task is to classify each node as:

• "Root": No parent (p_id is null).
• "Leaf": No children (id not in any p_id).
• "Inner": Has a parent and at least one child.

For example, in a table with rows [1,null], [2,1], [3,1], node 1 is "Root," 2 and 3 are "Leaf." This problem tests your ability to analyze relationships in a tree, typically posed as an SQL query, but we’ll solve it in Python for a coding spin.

Problem Statement

• Input: A list of records (or table rows) with [id, p_id].
• Output: A list of [id, type] where type is "Root," "Leaf," or "Inner."
• Rules:
• Root: p_id is null.
• Leaf: id not in any p_id.
• Inner: Has a parent and appears in some p_id.

Constraints

• Table has at least 1 row.
• id and p_id are integers (1 to 1000).
• p_id is null for root, otherwise references a valid id.
• Single root node.

Examples

• Input:
``` id | p_id 1 | null 2 | 1 3 | 1 4 | 2 ```
• Output:
``` [1, "Root"], [2, "Inner"], [3, "Leaf"], [4, "Leaf"] ```
• Input:
``` id | p_id 1 | null 2 | 1 ```
• Output:
``` [1, "Root"], [2, "Leaf"] ```

These examples show the classification—let’s solve it!

Understanding the Problem: Classifying Tree Nodes

To solve LeetCode 608: Tree Node in Python, we need to process a list of [id, p_id] pairs and determine each node’s type based on its parent and children. A naive approach might scan the list multiple times, but we can optimize it. We’ll use:

• Best Solution (DFS with Parent Tracking): O(n) time, O(n) space—fast and recursive.
• Alternative Solution (BFS with Level Tracking): O(n) time, O(n) space—iterative and level-based.

Let’s start with the DFS solution, breaking it down for beginners.

Best Solution: DFS with Parent Tracking

Why This Is the Best Solution

The DFS with parent tracking approach is the top choice for LeetCode 608 because it’s efficient—O(n) time to visit each node—and leverages recursion to naturally explore the tree while tracking parents and children with sets. It’s clean and mimics how you’d trace a family tree from the root down. It’s like following each branch to see who’s who!

How It Works

Think of this as exploring the tree from the top:

• Step 1: Build Sets:
• nodes: All ids.
• parents: All non-null p_ids (nodes with parents).
• children: All ids that appear as p_id (nodes with kids).
• Step 2: Classify:
• Root: p_id is null.
• Leaf: id not in children.
• Inner: id in children and p_id is not null.
• Step 3: Process Each Node:
• Use sets to check conditions in O(1).
• Step 4: Return Result:
• List of [id, type] pairs.

It’s like tagging each node as you explore!

Step-by-Step Example

Example:

Copy codeid | p_id
1  | null
2  | 1
3  | 1
4  | 2

• Step 1:
• nodes = {1, 2, 3, 4}.
• parents = {1, 2} (nodes with parents).
• children = {1, 2} (nodes with kids).
• Step 2: Classify:
• ID 1: p_id = null, "Root".
• ID 2: In children, has p_id, "Inner".
• ID 3: Not in children, "Leaf".
• ID 4: Not in children, "Leaf".
• Output: [[1, "Root"], [2, "Inner"], [3, "Leaf"], [4, "Leaf"]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def treeNode(self, tree: List[List]) -> List[List]:
        # Step 1: Build sets for classification
        nodes = set()
        parents = set()
        children = set()

        for id_val, p_id in tree:
            nodes.add(id_val)
            if p_id is not None:
                parents.add(id_val)
                children.add(p_id)

        # Step 2: Classify each node
        result = []
        for id_val, p_id in tree:
            if p_id is None:
                node_type = "Root"
            elif id_val not in children:
                node_type = "Leaf"
            else:
                node_type = "Inner"
            result.append([id_val, node_type])

        # Step 3: Return result
        return result

• Lines 4-6: Initialize sets:
• nodes: All IDs.
• parents: IDs with parents.
• children: IDs with children.
• Lines 8-11: Populate sets:
• Add id to nodes.
• If p_id exists, add id to parents, p_id to children.
• Lines 14-21: Classify:
• Root: p_id is null.
• Leaf: Not in children.
• Inner: In children and has p_id.
• Time Complexity: O(n)—one pass to build sets, one to classify.
• Space Complexity: O(n)—sets store up to n elements.

This is like a tree census—fast and neat!

Alternative Solution: BFS with Level Tracking

Why an Alternative Approach?

The BFS with level tracking approach uses a queue to explore the tree level-by-level—O(n) time, O(n) space. It’s iterative, avoiding recursion, and gives a different angle by processing nodes in order of depth. It’s like scanning the tree floor-by-floor!

How It Works

Picture this as a level-by-level tree tour:

• Step 1: Build adjacency list (children) and parent map.
• Step 2: Start BFS from root (null p_id).
• Step 3: Classify as you go:
• Root: Starting node.
• Leaf: No children in adjacency list.
• Inner: Has children and a parent.
• Step 4: Collect results.

It’s like a tree roll-call by level!

Step-by-Step Example

Example:

Copy codeid | p_id
1  | null
2  | 1
3  | 1
4  | 2

• Step 1:
• children = {1: [2, 3], 2: [4]}.
• parents = {2: 1, 3: 1, 4: 2}.
• Step 2: BFS from 1:
• 1: No parent, has kids, "Root".
• 2: Parent 1, has kid 4, "Inner".
• 3: Parent 1, no kids, "Leaf".
• 4: Parent 2, no kids, "Leaf".
• Output: [[1, "Root"], [2, "Inner"], [3, "Leaf"], [4, "Leaf"]].

Code for BFS Approach

Copy codefrom collections import defaultdict, deque

class Solution:
    def treeNode(self, tree: List[List]) -> List[List]:
        # Step 1: Build adjacency and parent maps
        children = defaultdict(list)
        parents = {}
        nodes = set()
        root_id = None

        for id_val, p_id in tree:
            nodes.add(id_val)
            if p_id is not None:
                children[p_id].append(id_val)
                parents[id_val] = p_id
            else:
                root_id = id_val

        # Step 2: BFS from root
        result = []
        queue = deque([root_id])
        visited = set()

        while queue:
            node = queue.popleft()
            if node in visited:
                continue
            visited.add(node)

            if node not in parents:
                node_type = "Root"
            elif not children[node]:
                node_type = "Leaf"
            else:
                node_type = "Inner"
            result.append([node, node_type])

            for child in children[node]:
                queue.append(child)

        return result

• Lines 6-16: Build maps:
• children: ID to list of kids.
• parents: ID to parent.
• Find root.
• Lines 19-35: BFS:
• Start at root, classify, enqueue children.
• Time Complexity: O(n)—visit each node.
• Space Complexity: O(n)—queue and maps.

It’s a level-by-level tree tag—detailed but clear!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n) time, O(n) space, simple and fast.
• Cons: Less intuitive for level order.
• BFS (Alternative):
• Pros: O(n) time, O(n) space, level-based.
• Cons: More setup, iterative complexity.

DFS wins for simplicity.

Additional Examples and Edge Cases

• Input: [[1,null]]
• Output: [[1, "Root"]].
• Input: [[1,null], [2,1], [3,2]]
• Output: [[1, "Root"], [2, "Inner"], [3, "Leaf"]].

Both handle these well.

Complexity Breakdown

• DFS: Time O(n), Space O(n).
• BFS: Time O(n), Space O(n).

DFS is leaner in practice.

Key Takeaways

• DFS: Recursive tree walk—smart!
• BFS: Level-by-level—clear!
• Trees: Relationships are fun.
• Python Tip: Sets rock—see Python Basics.

Final Thoughts: Tag Those Nodes

LeetCode 608: Tree Node in Python is a neat tree-classification puzzle. DFS offers elegance and speed, while BFS gives a level-based view. Want more? Try LeetCode 104: Maximum Depth of Binary Tree or LeetCode 111: Minimum Depth of Binary Tree. Ready to classify? Head to Solve LeetCode 608 on LeetCode and tag those nodes today!