1080. Insufficient Nodes in Root to Leaf Paths LeetCode Solution

In this guide, you will get 1080. Insufficient Nodes in Root to Leaf Paths LeetCode Solution with the best time and space complexity. The solution to Insufficient Nodes in Root to Leaf Paths problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Insufficient Nodes in Root to Leaf Paths solution in C++
Insufficient Nodes in Root to Leaf Paths solution in Java
Insufficient Nodes in Root to Leaf Paths solution in Python
Additional Resources

1080. Insufficient Nodes in Root to Leaf Paths LeetCode Solution image

Problem Statement of Insufficient Nodes in Root to Leaf Paths

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.
A leaf is a node with no children.

Example 1:

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]

Example 2:

Input: root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
Output: [5,4,8,11,null,17,4,7,null,null,null,5]

Example 3:

Input: root = [1,2,-3,-5,null,4,null], limit = -1
Output: [1,null,-3,4]

Constraints:

The number of nodes in the tree is in the range [1, 5000].
-105 <= Node.val <= 105
-109 <= limit <= 109

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h)

1080. Insufficient Nodes in Root to Leaf Paths LeetCode Solution in C++

class Solution {
 public:
  TreeNode* sufficientSubset(TreeNode* root, int limit) {
    if (root == nullptr)
      return nullptr;
    if (root->left == nullptr && root->right == nullptr)
      return root->val < limit ? nullptr : root;
    root->left = sufficientSubset(root->left, limit - root->val);
    root->right = sufficientSubset(root->right, limit - root->val);
    return root->left == nullptr && root->right == nullptr ? nullptr : root;
  }
};
/* code provided by PROGIEZ */

1080. Insufficient Nodes in Root to Leaf Paths LeetCode Solution in Java

class Solution {
  public TreeNode sufficientSubset(TreeNode root, int limit) {
    if (root == null)
      return null;
    if (root.left == null && root.right == null)
      return root.val < limit ? null : root;
    root.left = sufficientSubset(root.left, limit - root.val);
    root.right = sufficientSubset(root.right, limit - root.val);
    return root.left == null && root.right == null ? null : root;
  }
}
// code provided by PROGIEZ

1080. Insufficient Nodes in Root to Leaf Paths LeetCode Solution in Python

class Solution:
  def sufficientSubset(
      self,
      root: TreeNode | None,
      limit: int
  ) -> TreeNode | None:
    if not root:
      return None
    if not root.left and not root.right:
      return None if root.val < limit else root
    root.left = self.sufficientSubset(root.left, limit - root.val)
    root.right = self.sufficientSubset(root.right, limit - root.val)
    return None if not root.left and not root.right else root
 # code by PROGIEZ