LeetCode 1273 - Delete Tree Nodes

LeetCode Problem 1273

Difficulty: 🟡 Medium
Topics: Array, Tree, Depth-First Search, Breadth-First Search

Solution

Problem Understanding

The problem provides a tree rooted at node 0, represented in two parallel arrays: parent and value. The parent[i] array indicates the parent of the i-th node, with -1 denoting the root. The value[i] array gives the integer value of each node. The task is to remove all subtrees whose sum of node values is zero and then return the count of the remaining nodes in the tree.

For example, if a subtree rooted at some node x sums to zero, all of its children and the node itself are removed. The process continues recursively up the tree, as removing a subtree may cause its parent to also sum to zero. The constraints guarantee that the tree has at least one node and the input represents a valid tree. Node values can be negative, zero, or positive.

Key edge cases include subtrees that sum to zero at the leaf level, subtrees including the root that sum to zero, and trees where no nodes need removal.

Approaches

A brute-force approach would recursively calculate the sum of every subtree for every node and remove subtrees whose sum is zero. While correct, this approach would require recomputing sums repeatedly and could take O(n²) time in the worst case for deep trees.

The optimal approach leverages a Depth-First Search (DFS) traversal. By visiting children first, we can calculate the sum of each subtree in a bottom-up manner. If a subtree's sum is zero, it can be removed immediately. This ensures each node is visited exactly once, giving a linear O(n) time solution. We maintain a tree structure (using a map from parent to children) to simplify traversal and removal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Recomputes subtree sums repeatedly for each node
Optimal	O(n)	O(n)	DFS computes each subtree sum once and removes zero-sum subtrees

Algorithm Walkthrough

1. Build a tree representation using a dictionary (hash map) mapping each node to its children. This allows efficient access to all children of a node during traversal.
2. Define a DFS function that recursively calculates the sum of a subtree rooted at a given node.
3. For each node, recursively sum all values from its children using the DFS function. If a child's subtree sum is zero, skip counting its nodes (effectively removing the subtree).
4. Add the current node's value to the sum of its children to get the total subtree sum for the current node.
5. If the sum of the current node's subtree is zero, signal to the parent that this node should be removed.
6. After DFS finishes, return the total number of nodes that are part of non-zero subtrees.

Why it works: The DFS traversal ensures a post-order processing of nodes, calculating subtree sums before evaluating the parent. This guarantees that any subtree whose sum is zero is fully accounted for and removed. Each node is processed exactly once, so the algorithm is correct and efficient.

Python Solution

from typing import List, Dict

class Solution:
    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
        tree: Dict[int, List[int]] = {i: [] for i in range(nodes)}
        for i in range(1, nodes):
            tree[parent[i]].append(i)

        def dfs(node: int) -> int:
            subtotal = value[node]
            for child in tree[node]:
                child_sum = dfs(child)
                if child_sum == 0:
                    continue
                subtotal += child_sum
            return subtotal

        total_sum = dfs(0)

        def count_nodes(node: int) -> int:
            subtotal = value[node]
            count = 1
            for child in tree[node]:
                child_sum = dfs(child)
                if child_sum == 0:
                    continue
                count += count_nodes(child)
            if subtotal + sum(dfs(c) for c in tree[node] if dfs(c) != 0) == 0:
                return 0
            return count

        return count_nodes(0)

Explanation: We first build the adjacency list tree to represent children. The dfs function calculates subtree sums. The count_nodes function traverses the tree, counting nodes whose subtree sum is non-zero. Nodes with zero-sum subtrees are skipped. This implements the algorithm directly as discussed.

Go Solution

func deleteTreeNodes(nodes int, parent []int, value []int) int {
    tree := make([][]int, nodes)
    for i := 1; i < nodes; i++ {
        tree[parent[i]] = append(tree[parent[i]], i)
    }

    var dfs func(int) int
    dfs = func(node int) int {
        subtotal := value[node]
        for _, child := range tree[node] {
            subtotal += dfs(child)
        }
        return subtotal
    }

    var countNodes func(int) int
    countNodes = func(node int) int {
        subtotal := value[node]
        count := 1
        for _, child := range tree[node] {
            childSum := dfs(child)
            if childSum == 0 {
                continue
            }
            count += countNodes(child)
        }
        childSumTotal := 0
        for _, child := range tree[node] {
            cs := dfs(child)
            if cs != 0 {
                childSumTotal += cs
            }
        }
        if subtotal+childSumTotal == 0 {
            return 0
        }
        return count
    }

    return countNodes(0)
}

Explanation: The Go implementation mirrors Python, using slices instead of lists and recursive functions with closures. The adjacency list is built using make([][]int, nodes). Subtree sums are calculated with DFS, and nodes are counted if their subtree sum is non-zero.

Worked Examples

Example 1

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]

Tree representation:

0(1)
├─1(-2)
│ └─3(0)
└─2(4)
  ├─4(-2)
  ├─5(-1)
  └─6(-1)

Step-by-step:

1. DFS at leaf 3: sum = 0 → remove
2. DFS at leaf 4: sum = -2 → keep
3. DFS at leaf 5: sum = -1 → keep
4. DFS at leaf 6: sum = -1 → keep
5. DFS at node 2: 4 + (-2) + (-1) + (-1) = 0 → remove
6. DFS at node 1: -2 → keep
7. DFS at root 0: 1 + (-2) = -1 → keep

Remaining nodes: 0 and 1 → output 2.

Example 2

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-2]

Following the same procedure, only leaf 3 sums to zero and is removed. All other nodes remain → output 6.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited once during DFS traversal. Building the tree is O(n).
Space	O(n)	Tree representation uses O(n) space. Recursion stack depth is at most O(n).

The reasoning is that DFS computes subtree sums and counts nodes efficiently. Each node is visited exactly twice: once for sum calculation and once for counting remaining nodes. Space is dominated by the adjacency list and recursion stack.

Test Cases

# Provided examples
assert Solution().deleteTreeNodes(7, [-1,0,0,1,2,2,2], [1,-2,4,0,-2,-1,-1]) == 2  # Example 1
assert Solution().deleteTreeNodes(7, [-1,0,0,1,2,2,2], [1,-2,4,0,-2,-1,-2]) == 6  # Example 2

# Edge cases
assert Solution().deleteTreeNodes(1, [-1], [0]) == 0  # Single node, zero value
assert Solution().deleteTreeNodes(1, [-1], [5]) == 1  # Single node, non-zero value
assert Solution().deleteTreeNodes(3, [-1,0,0], [1,-1,0]) == 1  # Root with zero-sum children

# Larger tree
assert Solution().deleteTreeNodes(5, [-1,0,0,1,1], [1,-1,1,0,0]) == 3

Test	Why
Single node, zero value	Ensures algorithm handles smallest tree
Single node, non-zero	Ensures correct count when root remains
Root with zero-sum children	Validates recursive removal
Larger tree	Tests correctness on non-trivial tree

Edge Cases

Single Node Tree: If the tree contains only the root, its value alone determines whether it is removed. Implementation correctly returns 0 if root sum is zero, otherwise 1.

Leaf Nodes with Zero Value: Leaf