LeetCode 608 - Tree Node

This problem gives us a database table named Tree, where each row represents a node in a tree structure. Every node has a unique identifier id and a pid column that stores the identifier of its parent node.

leetcodemediumdatabase

LeetCode Problem 608

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem gives us a database table named Tree, where each row represents a node in a tree structure. Every node has a unique identifier id and a p_id column that stores the identifier of its parent node.

The task is to classify every node into one of three categories:

  • "Root" if the node has no parent, meaning p_id IS NULL
  • "Leaf" if the node has no children
  • "Inner" if the node has both a parent and at least one child

In simpler terms, we need to examine each node and determine its structural role inside the tree.

The input represents a valid tree. This guarantee is important because it means:

  • There is exactly one root node
  • There are no cycles
  • Every non-root node has exactly one parent
  • The relationships form a connected tree

The expected output is a result table containing two columns:

  • id, the node identifier
  • type, one of "Root", "Leaf", or "Inner"

The order of the returned rows does not matter.

The key challenge is determining whether a node has children. The p_id column tells us who a node's parent is, but to know whether a node is a leaf or inner node, we must identify whether its id appears as another node's p_id.

Several edge cases are important to consider. A tree with only one node is both technically a root and a leaf, but the problem definition prioritizes "Root", so the correct classification is "Root". Another important case is nodes with children but no parent, which must always be labeled "Root". Finally, nodes with parents but no children are "Leaf" nodes.

Since this is a Database problem, the goal is to express this classification efficiently in SQL.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to inspect each node independently and determine its type using repeated searches.

For every row in the Tree table, we could:

  1. Check whether p_id IS NULL. If yes, classify it as "Root".
  2. Otherwise, scan the table to see whether any row has p_id = current id.
  3. If children exist, classify it as "Inner".
  4. Otherwise, classify it as "Leaf".

This approach is correct because every node is evaluated against the exact problem definition. However, it is inefficient because each node may require scanning the entire table to determine whether it has children.

If there are n nodes, checking children for each node takes O(n) work, producing a total complexity of O(n²).

Optimal Approach

The key observation is that we do not need to repeatedly search for child relationships. Instead, we can use a single query to identify all node IDs that appear as a parent.

A node is a parent if its id exists in the set of non-null p_id values.

Using SQL, this naturally translates into a CASE statement:

  • If p_id IS NULL, classify as "Root"
  • Else if id exists among parent IDs, classify as "Inner"
  • Otherwise, classify as "Leaf"

The important optimization is that the database can efficiently evaluate membership using a subquery or join, avoiding repeated manual scans.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Repeatedly scans table for every node
Optimal O(n) O(n) Uses parent ID lookup through subquery

Algorithm Walkthrough

  1. Start by iterating through every node in the Tree table.
  2. For each node, first check whether p_id IS NULL. This condition identifies the root node because a root has no parent.
  3. If the node is not a root, determine whether it has children. We do this by checking whether the current node's id appears in the set of all non-null p_id values. If it appears there, it means at least one node references it as a parent.
  4. If the node has children, classify it as "Inner" because it is neither a root nor a leaf.
  5. Otherwise, classify it as "Leaf" because no node depends on it.
  6. Return the result table with columns id and type.

Why it works

The correctness follows directly from the definitions of node types. Every node falls into exactly one of three mutually exclusive categories:

  • p_id IS NULL uniquely identifies the root.
  • A node appearing as a parent of another node must have children, making it an inner node unless it is the root.
  • Any remaining node has no children, making it a leaf.

Because every node is classified according to these precise rules, the algorithm always produces the correct result.

Python Solution

Although this is a SQL problem on LeetCode, the platform sometimes requests a Python representation for consistency. The actual accepted solution is an SQL query.

class Solution:
    def treeNode(self):
        return """
        SELECT
            id,
            CASE
                WHEN p_id IS NULL THEN 'Root'
                WHEN id IN (
                    SELECT DISTINCT p_id
                    FROM Tree
                    WHERE p_id IS NOT NULL
                ) THEN 'Inner'
                ELSE 'Leaf'
            END AS type
        FROM Tree
        """

The implementation uses a SQL CASE expression to classify nodes.

The first condition checks p_id IS NULL, immediately identifying root nodes.

The second condition checks whether the node ID exists among parent IDs. The subquery retrieves all distinct non-null p_id values, which correspond to nodes that have at least one child.

If neither condition matches, the node has no children and is therefore labeled "Leaf".

Using DISTINCT is not strictly required for correctness, but it avoids redundant duplicate parent IDs.

Go Solution

For database problems, Go is generally represented as the SQL query string used in a submission wrapper.

package main

func treeNode() string {
	return `
SELECT
    id,
    CASE
        WHEN p_id IS NULL THEN 'Root'
        WHEN id IN (
            SELECT DISTINCT p_id
            FROM Tree
            WHERE p_id IS NOT NULL
        ) THEN 'Inner'
        ELSE 'Leaf'
    END AS type
FROM Tree
`
}

The Go version simply returns the SQL query as a raw string literal. Unlike algorithmic problems, there is no tree traversal or memory management required because the database engine performs the computation.

There are no Go-specific concerns such as slices, maps, integer overflow, or nil handling because the core logic is SQL-based.

Worked Examples

Example 1

Input table:

id p_id
1 NULL
2 1
3 1
4 2
5 2

First, gather all non-null parent IDs:

{1, 2}

Now classify each node.

Node p_id Is Root? In Parent Set? Result
1 NULL Yes Yes Root
2 1 No Yes Inner
3 1 No No Leaf
4 2 No No Leaf
5 2 No No Leaf

Final output:

id type
1 Root
2 Inner
3 Leaf
4 Leaf
5 Leaf

Example 2

Input table:

id p_id
1 NULL

First, collect parent IDs:

{}

Now classify:

Node p_id Is Root? In Parent Set? Result
1 NULL Yes No Root

Final output:

id type
1 Root

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is processed once, and parent lookup is efficient
Space O(n) Parent IDs conceptually form a lookup set

The dominant work comes from scanning the table and identifying parent IDs. In practice, database engines optimize the IN subquery efficiently, often using indexes or hash-based membership checks.

Test Cases

Since this is a SQL problem, test cases are best represented as input tables and expected outputs.

# Example 1
tree = [
    (1, None),
    (2, 1),
    (3, 1),
    (4, 2),
    (5, 2)
]
expected = {
    1: "Root",
    2: "Inner",
    3: "Leaf",
    4: "Leaf",
    5: "Leaf"
}

# Example 2, single node tree
tree = [
    (1, None)
]
expected = {
    1: "Root"
}

# Root with one child
tree = [
    (1, None),
    (2, 1)
]
expected = {
    1: "Root",
    2: "Leaf"
}

# Deep chain
tree = [
    (1, None),
    (2, 1),
    (3, 2),
    (4, 3)
]
expected = {
    1: "Root",
    2: "Inner",
    3: "Inner",
    4: "Leaf"
}

# Wide tree
tree = [
    (1, None),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1)
]
expected = {
    1: "Root",
    2: "Leaf",
    3: "Leaf",
    4: "Leaf",
    5: "Leaf"
}
Test Why
Example 1 Validates mixed node types
Example 2 Tests single-node tree edge case
Root with one child Ensures root classification overrides child existence
Deep chain Verifies inner nodes in linear trees
Wide tree Confirms multiple leaf detection

Edge Cases

Single Node Tree

A tree with only one node is an important corner case. Technically, the node has no parent and no children, which could make classification ambiguous. The problem definition resolves this by prioritizing "Root". Since the implementation checks p_id IS NULL first, the node is correctly labeled "Root".

Root Node With Children

The root node can also have children. A naive implementation might mistakenly classify it as "Inner" because it appears in the parent set. This implementation avoids that bug by checking for root status first. Once p_id IS NULL is true, the node is immediately classified as "Root".

Nodes With No Children

Leaf nodes are identified indirectly, by exclusion. A node that is not the root and does not appear as a parent ID must be a leaf. This logic ensures correctness even when many nodes share the same parent or when the tree is highly unbalanced.