LeetCode 3054 - Binary Tree Nodes

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to classify nodes in a binary tree based on their role in the tree structure. The input is represented as a table Tree with two columns: N representing the node value, and P representing the parent node value. A null parent indicates that the node is the root. Each node is guaranteed to have a unique value, and the tree structure does not have cycles.

The expected output is a table that lists each node (N) along with its type: Root if it has no parent, Leaf if it has no children, and Inner if it has both a parent and at least one child. The results must be sorted by node value in ascending order.

Important edge cases include trees with a single node, nodes with no children (leaves), nodes with only one child, and trees where the root is not the first row in the input. The problem guarantees that the tree is valid and there is exactly one root.

Approaches

The brute-force approach would iterate over every node and, for each node, check every other node to see if it is a parent or child. If a node has null as parent, it is classified as Root; if no other nodes reference it as a parent, it is a Leaf; otherwise, it is Inner. This approach is correct but inefficient because it requires comparing every pair of nodes, resulting in O(n^2) time complexity.

The optimal approach relies on set-based classification. First, identify the root by checking which node has a null parent. Next, collect all nodes that appear as a parent in a hash set. Any node in this set is either Root or Inner. Nodes not in this set are Leaf. This approach uses hashing for constant-time membership checks, which reduces time complexity to O(n) and makes the solution scalable for larger trees.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Check every node against every other node to determine children and parent relationships
Optimal	O(n)	O(n)	Use a hash set to track parent nodes and classify nodes based on presence in the set

Algorithm Walkthrough

Initialize an empty set called parents to track all nodes that appear as a parent in the table.
Iterate over each row in the Tree table. For every row, if the parent P is not null, add it to the parents set. This ensures we know which nodes have children.
Iterate over the Tree table again. For each node N:

If P is null, classify the node as Root.
Otherwise, if N is in the parents set, classify the node as Inner.
Otherwise, classify the node as Leaf.

Collect the results as pairs of (N, Type) and sort them by node value in ascending order.
Return the sorted result.

This algorithm works because the root is uniquely defined by having a null parent, leaves are nodes that never appear as a parent, and all other nodes are inner nodes. By storing parents in a set, we guarantee constant-time lookups and ensure correctness.

Python Solution

import pandas as pd

class Solution:
    def classifyNodes(self, Tree: pd.DataFrame) -> pd.DataFrame:
        parents = set(Tree['P'].dropna())
        result = []

        for _, row in Tree.iterrows():
            node = row['N']
            parent = row['P']
            if pd.isna(parent):
                node_type = 'Root'
            elif node in parents:
                node_type = 'Inner'
            else:
                node_type = 'Leaf'
            result.append({'N': node, 'Type': node_type})
        
        return pd.DataFrame(result).sort_values('N').reset_index(drop=True)

In this Python implementation, we first extract all parent values into a set, excluding nulls. Then, we iterate over each node and classify it based on whether it is the root (parent is null), inner (node appears in the parent set), or leaf (node does not appear in the parent set). Finally, the results are sorted by node value for correct output.

Go Solution

package main

import (
	"sort"
)

type TreeNode struct {
	N int
	P *int
}

type Result struct {
	N    int
	Type string
}

func classifyNodes(tree []TreeNode) []Result {
	parentSet := make(map[int]bool)
	for _, node := range tree {
		if node.P != nil {
			parentSet[*node.P] = true
		}
	}

	results := make([]Result, 0, len(tree))
	for _, node := range tree {
		var nodeType string
		if node.P == nil {
			nodeType = "Root"
		} else if parentSet[node.N] {
			nodeType = "Inner"
		} else {
			nodeType = "Leaf"
		}
		results = append(results, Result{N: node.N, Type: nodeType})
	}

	sort.Slice(results, func(i, j int) bool {
		return results[i].N < results[j].N
	})
	return results
}

In Go, we handle null parents using pointers. The algorithm mirrors the Python version: first collect all parent nodes into a map for fast lookup, then classify nodes accordingly. We use sort.Slice to sort results by node value.

Worked Examples

Given the example input:

N | P
1 | 2
3 | 2
6 | 8
9 | 8
2 | 5
8 | 5
5 | null

Step 1: Build the parent set → {2, 5, 8}

Step 2: Classify nodes:

Node 1 → parent 2, 1 not in parent set → Leaf
Node 2 → parent 5, 2 in parent set → Inner
Node 3 → parent 2, 3 not in parent set → Leaf
Node 5 → parent null → Root
Node 6 → parent 8, 6 not in parent set → Leaf
Node 8 → parent 5, 8 in parent set → Inner
Node 9 → parent 8, 9 not in parent set → Leaf

Step 3: Sort by node value → [1, 2, 3, 5, 6, 8, 9]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass to build parent set, another pass to classify nodes, plus O(n log n) for sorting
Space	O(n)	Parent set stores up to n elements, result list stores n nodes

The algorithm is efficient because it avoids nested iterations over nodes and uses hash-based lookups for classification.

Test Cases

import pandas as pd

# Example 1
df1 = pd.DataFrame({'N':[1,3,6,9,2,8,5],'P':[2,2,8,8,5,5,None]})
expected1 = pd.DataFrame({'N':[1,2,3,5,6,8,9],'Type':['Leaf','Inner','Leaf','Root','Leaf','Inner','Leaf']})
assert Solution().classifyNodes(df1).equals(expected1)  # standard example

# Single node tree
df2 = pd.DataFrame({'N':[1],'P':[None]})
expected2 = pd.DataFrame({'N':[1],'Type':['Root']})
assert Solution().classifyNodes(df2).equals(expected2)  # root-only

# Chain tree
df3 = pd.DataFrame({'N':[1,2,3],'P':[2,3,None]})
expected3 = pd.DataFrame({'N':[1,2,3],'Type':['Leaf','Inner','Root']})
assert Solution().classifyNodes(df3).equals(expected3)  # linear tree

# All leaves except root
df4 = pd.DataFrame({'N':[1,2,3,4],'P':[None,1,1,1]})
expected4 = pd.DataFrame({'N':[1,2,3,4],'Type':['Root','Leaf','Leaf','Leaf']})
assert Solution().classifyNodes(df4).equals(expected4)  # root with many leaves

Test	Why
Example 1	Validates standard tree classification
Single node	Ensures root-only tree works
Chain tree	Checks linear parent-child relationships
Root with many leaves	Tests multiple leaf children of root

Edge Cases

A single-node tree is an important edge case because the algorithm must correctly classify a root with no children. The implementation handles this by checking if the parent is null.

A tree where all non-root nodes are leaves tests that inner nodes are not incorrectly classified. The parent set ensures that only nodes appearing as parents are considered inner.

A linear chain tree (every node has exactly one child) tests that the algorithm correctly identifies inner nodes in a sequence. The parent set captures the parent-child relationships and guarantees accurate classification even in degenerate trees.