We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Delete Tree Nodes

Number: 1201

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given a tree with nodes numbered from 0 to n-1 (with 0 as the root), each node has a value provided in the array value[]. The parent array (with parent[0] = -1) indicates the tree structure. The task is to remove every subtree (i.e. a node and all its descendants) whose sum of node values is zero and then return the total number of nodes remaining in the tree.

Key Insights

  • Construct the tree using an adjacency list from the given parent array.
  • Use depth-first search (DFS) to traverse the tree in a postorder manner (process children before the parent).
  • At each node, compute the total sum of the subtree (current node and its descendants).
  • If the subtree sum is zero, consider all those nodes removed (i.e. contribute zero to the count).
  • Finally, return the number of nodes retained (subtrees with non-zero sum).

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since each node is visited once. Space Complexity: O(n), due to the recursion stack and auxiliary data structures (like the children list).

Solution

The solution involves first converting the parent list into a mapping of node to its children. Then, employing DFS from the tree's root, we compute both the sum of the subtree and the count of nodes that remain (if the subtree sum is zero, we remove that entire subtree). The DFS returns a tuple (subtree sum, count) for each node. This approach ensures every node is processed only once and allows the algorithm to correctly “prune” subtrees with a sum of zero.

Code Solutions

# Python solution for Delete Tree Nodes

def deleteTreeNodes(nodes, parent, value):
    # Build the children mapping for each node.
    children = [[] for _ in range(nodes)]
    for child in range(1, nodes):
        par = parent[child]
        children[par].append(child)
    
    # DFS function returns a tuple: (subtree sum, count of nodes remaining)
    def dfs(node):
        total_sum = value[node]
        node_count = 1  # Counting the current node
        # Process all children
        for child in children[node]:
            child_sum, child_count = dfs(child)
            total_sum += child_sum
            node_count += child_count
        
        # If subtree sum equals 0, delete this subtree by returning 0 count.
        if total_sum == 0:
            return (0, 0)
        else:
            return (total_sum, node_count)
    
    # Get results from root node.
    _, remaining_nodes = dfs(0)
    return remaining_nodes

# Example usage:
# nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
# Expected output: 2
print(deleteTreeNodes(7, [-1,0,0,1,2,2,2], [1,-2,4,0,-2,-1,-1]))
← Back to All Questions