MediumNo. 1080
Insufficient Nodes in Root to Leaf Paths — LeetCode 1080 Python Solution
- Pattern
- Tree Traversal
- Topics
- Tree, Depth-First Search, Binary Tree
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Given the root of a binary tree and an integer limit, delete all insufficient nodes in the tree simultaneously, and return the root of the resulting binary tree. A node is insufficient if every root to leaf path intersecting this node has a sum strictly less than limit.
Example
- Input
- root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
- Output
- [1,2,3,4,null,null,7,8,9,null,14]
Python solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sufficientSubset(
self, root: Optional[TreeNode], limit: int
) -> Optional[TreeNode]:
if root is None:
return None
limit -= root.val
if root.left is None and root.right is None:
return None if limit > 0 else root
root.left = self.sufficientSubset(root.left, limit)
root.right = self.sufficientSubset(root.right, limit)
return None if root.left is None and root.right is None else rootComplexity
- Time
- O(V+E)
- Space · auxiliary
- O(V)
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1080. Insufficient Nodes in Root to Leaf Paths is filed here because LeetCode tags it Tree and Binary 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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0098 | Validate Binary Search Tree | Medium |
| 0099 | Recover Binary Search Tree | Medium |
| 0100 | Same Tree | Easy |
| 0101 | Symmetric Tree | Easy |
| 0104 | Maximum Depth of Binary Tree | Easy |
| 0110 | Balanced Binary Tree | Easy |
Frequently asked questions
- How hard is LeetCode 1080. Insufficient Nodes in Root to Leaf Paths?
LeetCode 1080. Insufficient Nodes in Root to Leaf Paths is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1080. Insufficient Nodes in Root to Leaf Paths?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 1080. Insufficient Nodes in Root to Leaf Paths?
The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 1080. Insufficient Nodes in Root to Leaf Paths cover?
LeetCode 1080. Insufficient Nodes in Root to Leaf Paths is tagged Tree, Depth-First Search and Binary Tree on LeetCode.