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.

Description Hints 3 Solution Video 11:46

1273. Delete Tree Nodes

Medium61.2% acceptance1 companyPremium elsewhere, free here

A tree rooted at node 0 is given as follows:

The number of nodes is nodes;
The value of the i^th node is value[i];
The parent of the i^th 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 <= 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⁵
The given input is guaranteed to represent a valid tree.

Asked at 1 company

Microsoft

Topics

Hints open one at a time

Hint 1

Traverse the tree using depth first search.

Hint 2

Find for every node the sum of values of its sub-tree.

Hint 3

Traverse the tree again from the root and return once you reach a node with zero sum of values in its sub-tree.

11:46

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

7
[-1,0,0,1,2,2,2]
[1,-2,4,0,-2,-1,-1]

Input

7
[-1,0,0,1,2,2,2]
[1,-2,4,0,-2,-1,-2]

Your code is saved on this device.Solution