How hard is LeetCode 1273. Delete Tree Nodes?

LeetCode 1273. Delete Tree Nodes is rated Medium on LeetCode.

What is the time complexity of LeetCode 1273. Delete Tree Nodes?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1273. Delete Tree Nodes?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1273. Delete Tree Nodes cover?

LeetCode 1273. Delete Tree Nodes is tagged Tree, Depth-First Search, Breadth-First Search and Array on LeetCode.

Is LeetCode 1273. Delete Tree Nodes a premium problem?

Yes. LeetCode 1273. Delete Tree Nodes is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Delete Tree Nodes — LeetCode 1273 Python Solution

MediumLeetCode PremiumTreeDepth-First SearchBreadth-First SearchArray

Problem: #1273
Pattern: Tree Traversal
Reading time: 3 min
Source: leetcode.com

The 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.

Example

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

Python solution

Python

class Solution:
    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
        def dfs(i):
            s, m = value[i], 1
            for j in g[i]:
                t, n = dfs(j)
                s += t
                m += n
            if s == 0:
                m = 0
            return (s, m)

        g = defaultdict(list)
        for i in range(1, nodes):
            g[parent[i]].append(i)
        return dfs(0)[1]

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1273. Delete Tree Nodes is filed here because LeetCode tags it Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1273. Delete Tree Nodes?: LeetCode 1273. Delete Tree Nodes is rated Medium on LeetCode.
What is the time complexity of LeetCode 1273. Delete Tree Nodes?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1273. Delete Tree Nodes?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1273. Delete Tree Nodes cover?: LeetCode 1273. Delete Tree Nodes is tagged Tree, Depth-First Search, Breadth-First Search and Array on LeetCode.
Is LeetCode 1273. Delete Tree Nodes a premium problem?: Yes. LeetCode 1273. Delete Tree Nodes is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.