Delete Tree Nodes - Practice Coding Problems

Delete Tree Nodes - Problem

A tree rooted at node 0 is given as follows:

The number of nodes is nodes
The value of the ith node is value[i]
The parent of the ith node is parent[i]

Remove every subtree whose sum of values of nodes is zero.

Return the number of the remaining nodes in the tree.

Input & Output

Example 1 — Basic Tree Pruning

$ Input: parent = [-1,0,0,1,1,1,1], value = [1,-3,4,0,-2,-1,-2]

› Output: 2

💡 Note: Node 3 and its descendants form subtree with sum 0 + (-2) + (-1) + (-2) = -5. Wait, let me recalculate: Node 1 has value -3, children 3,4,5,6. Subtree sum = -3 + 0 + (-2) + (-1) + (-2) = -8. Only nodes 0 and 2 remain with values 1 and 4.

Example 2 — Single Node Tree

$ Input: parent = [-1], value = [0]

› Output: 0

💡 Note: Root node has value 0, so entire tree is removed. No nodes remain.

Example 3 — No Removal Needed

$ Input: parent = [-1,0,1], value = [1,2,3]

› Output: 3

💡 Note: No subtree has sum 0. All nodes remain: root(1) -> child(2) -> grandchild(3)

Constraints

1 ≤ nodes ≤ 10⁴
parent.length == nodes
0 ≤ parent[i] ≤ nodes - 1
parent[0] == -1 which indicates that 0 is the root
value.length == nodes
-10⁵ ≤ value[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with parent array and node values

Calculate Sums

Find subtrees with sum = 0

Remove & Count

Delete zero-sum subtrees, count remaining

Key Takeaway

🎯 Key Insight: Use post-order DFS to calculate subtree sums and prune zero-sum subtrees in single traversal

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is to use post-order DFS traversal to calculate subtree sums from leaves to root, marking zero-sum subtrees for removal in a single pass. Best approach is DFS post-order with Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Multiple Tree Traversals	O(n²)	O(n)	Repeatedly traverse tree to find and remove zero-sum subtrees
DFS Post-Order Traversal	O(n)	O(n)	Single DFS pass calculating subtree sums and pruning zero-sum subtrees

Brute Force - Multiple Tree Traversals — Algorithm Steps

Build tree from parent array
Traverse tree to find zero-sum subtrees
Remove found subtrees
Repeat until no more zero-sum subtrees exist

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Tree

Construct tree from parent array

Find Zero Sums

Traverse tree to find zero-sum subtrees

Remove & Repeat

Remove found subtrees and scan again

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 1000

int children[MAX_N][MAX_N];
int childCount[MAX_N];
int value[MAX_N];
bool removed[MAX_N];
int n;

int calculateSum(int node) {
    if (removed[node]) return 0;
    int total = value[node];
    for (int i = 0; i < childCount[node]; i++) {
        total += calculateSum(children[node][i]);
    }
    return total;
}

void markRemoved(int node) {
    removed[node] = true;
    for (int i = 0; i < childCount[node]; i++) {
        markRemoved(children[node][i]);
    }
}

int solution(int parent[], int val[], int size) {
    n = size;
    if (n == 0) return 0;
    
    memset(childCount, 0, sizeof(childCount));
    memset(removed, false, sizeof(removed));
    memcpy(value, val, sizeof(int) * n);
    
    for (int i = 1; i < n; i++) {
        int p = parent[i];
        children[p][childCount[p]++] = i;
    }
    
    bool changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < n; i++) {
            if (!removed[i] && calculateSum(i) == 0) {
                markRemoved(i);
                changed = true;
            }
        }
    }
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!removed[i]) count++;
    }
    return count;
}

int main() {
    // Simple parsing - assume small arrays for C implementation
    int parent[MAX_N], val[MAX_N];
    int size;
    scanf("%d", &size);
    for (int i = 0; i < size; i++) {
        scanf("%d", &parent[i]);
    }
    for (int i = 0; i < size; i++) {
        scanf("%d", &val[i]);
    }
    
    printf("%d\n", solution(parent, val, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

May need O(n) iterations, each requiring O(n) traversal

⚠ Quadratic Growth

Space Complexity

O(n)

Tree structure and visited arrays

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Multiple Tree Traversals — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler