Skip to main content
Talentd

Delete Tree Nodes - Solution & Explanation

MediumPremiumFree on FleetCodeArrayTreeDepth-First SearchBreadth-First Search7 min readAsked at: Microsoft
Practice this problem

Problem Statement

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.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= nodes <= 104
  • parent.length == nodes
  • 0 <= parent[i] <= nodes - 1
  • parent[0] == -1 which indicates that 0 is the root.
  • value.length == nodes
  • -105 <= value[i] <= 105
  • The given input is guaranteed to represent a valid tree.

Approach Overview

Problem Overview: You are given a tree with n nodes represented by a parent array and a value array. If the sum of values in any subtree becomes zero, that entire subtree must be deleted. The goal is to return the number of nodes remaining after all zero-sum subtrees are removed.

Approach 1: Postorder DFS on Tree (O(n) time, O(n) space)

The key observation: whether a node stays in the tree depends on the total sum of its entire subtree. This naturally leads to a postorder traversal using Depth-First Search. First build an adjacency list from the parent array so you can traverse children efficiently. During DFS, recursively compute the subtree sum and the node count for each child. If a child's subtree sum becomes zero, you discard that subtree by not adding its sum or count to the parent. Otherwise, accumulate both values. After processing all children, if the current subtree sum equals zero, return (0, 0) to signal that the whole subtree should be removed.

This works because postorder traversal ensures children are processed before the parent. Every node is visited exactly once, so the time complexity is O(n) and the recursion stack plus adjacency list uses O(n) space. This is the cleanest and most common solution for problems combining tree traversal with subtree aggregation.

Approach 2: Leaf Processing with Reverse BFS / Topological Order (O(n) time, O(n) space)

Another way to think about the problem is processing the tree from leaves upward. Track the number of children for each node and push all leaves into a queue. Using a strategy similar to Breadth-First Search, process nodes whose children are already handled. Each node contributes its value to its parent unless its accumulated subtree sum becomes zero. If the sum is zero, the subtree is removed and contributes nothing upward. Otherwise, propagate the sum and node count to the parent.

This approach simulates a bottom-up evaluation without recursion. It works well when recursion depth could be large or when you want an iterative solution. The complexity remains O(n) time since each node is processed once, with O(n) space for queues and auxiliary arrays.

Recommended for interviews: The postorder DFS approach is what most interviewers expect. It directly models the "compute subtree result before parent" pattern that appears frequently in tree problems. Starting with a DFS solution demonstrates strong understanding of subtree aggregation. Mentioning the bottom-up BFS/topological variant shows deeper insight into alternative tree processing strategies.

Solution

First, we convert the tree into a graph g, where g[i] represents all the child nodes of node i.

Then we design a function dfs(i), which represents the number of nodes and the sum of the weights in the subtree rooted at node i. The answer is dfs(0)[1].

In this function, we recursively calculate the number of nodes and the sum of the weights in the subtree rooted at each child node j, and then accumulate these values. If the accumulated value is zero, we set the number of nodes in this subtree to zero. Finally, we return the number of nodes and the sum of the weights in the subtree rooted at node i.

The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the tree.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Postorder DFS (Subtree Aggregation)O(n)O(n)General case. Clean recursive solution that naturally computes subtree sums.
Leaf Processing with Reverse BFSO(n)O(n)Useful when avoiding recursion or when processing the tree bottom-up iteratively.

Video Solution

Leetcode 1273. Delete Tree Nodes (Topological sort) • LetsCode • 44 views views

Frequently Asked Questions

Is Delete Tree Nodes easy or hard?
Delete Tree Nodes is generally considered a medium-level tree problem. The challenge lies in recognizing that subtree sums must be computed using postorder traversal and that entire subtrees should be pruned when the sum becomes zero.
Delete Tree Nodes Python/Java solution
Most implementations build a children list and run a recursive DFS that returns subtree sum and node count. The same logic works across Python, Java, C++, and Go with O(n) time complexity.
How to solve Delete Tree Nodes in O(n)?
Build a child adjacency list from the parent array and run a postorder DFS. For each node, recursively compute the total subtree sum and node count from its children. If the final subtree sum equals zero, discard the subtree; otherwise return the accumulated sum and count upward.
What is the best approach for Delete Tree Nodes?
The best approach is a postorder DFS that computes the sum and size of each subtree. If a subtree sum becomes zero, it is removed by returning (0,0) to the parent. Each node is visited once, giving O(n) time complexity and O(n) space for recursion and adjacency lists.
Is Delete Tree Nodes asked at Google/Amazon/Meta?
Tree DFS problems involving subtree aggregation frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem test your ability to compute subtree properties using postorder traversal and pruning logic.
What data structure is used in Delete Tree Nodes?
The solution uses a tree represented through an adjacency list built from the parent array. Traversal is typically done using Depth-First Search (DFS), though a Breadth-First Search style bottom-up processing approach can also be used.
What is the time complexity of Delete Tree Nodes?
The optimal solution runs in O(n) time because every node in the tree is processed exactly once during traversal. Building the adjacency list also takes O(n). Space complexity is O(n) due to the recursion stack and child lists.

Ready to solve this problem?

Practice Delete Tree Nodes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays