1080. Insufficient Nodes in Root to Leaf Paths

Problem Description

The given LeetCode problem deals with a binary tree and a specified limit value. The objective is to examine all paths from the root to the leaves, and for each node, determine if it is part of any path where the sum of the node values meets or exceeds the limit. If a node does not lie on such a path, it is considered 'insufficient' and should be deleted. After deleting all insufficient nodes, the modified binary tree is returned.

The key point is to understand that a node is 'insufficient' if every path through that node has a sum of values less than the limit – meaning it doesn't support any path that would satisfy the threshold. Keep in mind, leaf nodes are the ones with no children.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

Yes: The binary tree can be viewed as a specific type of graph where nodes (tree elements) are connected by edges (branches).

Is it a tree?

Yes: By definition, the problem describes the binary tree structure, indicating we are working with a tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: Although trees are acyclic and directed, the nature of the problem, which involves determining if paths meet a specific sum condition, suggests a method focusing on paths rather than properties specific to DAGs (like topological sorts).

Is the problem related to shortest paths?

No: The task involves summing values along paths and does not concern finding shortest paths.

Does the problem involve connectivity?

No: The primary challenge is summing node values from root to leaves, not determining connectivity between nodes.

Therefore, the flowchart leads us to conclude that Depth-First Search (DFS) is appropriate. DFS is ideal for tree traversals, particularly when needing to evaluate or manipulate every path from root to leaf, as required by this problem where paths not meeting a minimum sum are pruned.

Intuition

The intuition behind the solution revolves around recursively checking each node, starting from the root and going down to the leaves. As we traverse path by path, we subtract the node's value from the limit, effectively calculating the sum of the path as we progress. If we reach a leaf node (a node with no children), we check if the updated limit is greater than 0. If it is, then the path sum up to this node was not sufficient, and this leaf node is deleted (return None).

For non-leaf nodes, we apply this process recursively to both the left and right children. After assessing both subtrees, we have to determine if the current node becomes a leaf node as a result (i.e., both children are None after potentially deleting insufficient nodes). If after deletion of child nodes the current node is a leaf and it was insufficient, we delete the current node as well (again, return None); otherwise, we keep it.

The process continues until all nodes are visited. If the root itself turns out to be insufficient, the result will be an empty tree (i.e., the root would also be returned as None).

The solution elegantly side-steps the need to keep track of all paths from the root to each node by updating the limit on the go and utilizing the recursive stack to backtrack once a leaf has been reached or a subtree has been pruned.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

To solve this problem, a depth-first search (DFS) algorithm is employed. This recursive approach allows us to traverse the tree from the root node to the leaves, checking each node along the way to see if it is sufficient with respect to the limit.

Here's a step-by-step explanation of the code:

The sufficientSubset function is defined with root (the current node) and limit (the remaining path sum before reaching insufficiency) as parameters.
The base case for the recursion is checking if the current root node is None. If it is, we return None, effectively ending that path.
For each node, we subtract the node's value from the limit. This step accumulates the sum of node values on the current path.
If the current node is a leaf (root.left is None and root.right is None), we check if the reduced limit is positive. If it is positive, then this path does not satisfy the sum requirement, so we return None to delete this leaf. Otherwise, we return the current node itself as this node is sufficient and should remain.
If the current node is not a leaf, we recursively call sufficientSubset on both the left and right children of the node. Here, we pass the updated limit after subtracting the current node's value.
After the recursive calls, we need to determine if the current node should be deleted. This is based on whether both of its children are None after the potential deletion of insufficient nodes. If both children are None, we return None, deleting the current node. If at least one child remains, we return the current node itself, as it supports a sufficient path.
This recursive process will prune all insufficient nodes from the tree and, once the recursion stack unwinds back to the root, will return the new tree rooted at the (potentially new) 'root'.

This elegant approach ensures we only traverse each node once, giving us an efficient time complexity proportional to the number of nodes in the tree, which is O(n).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple binary tree alongside a limit to see how the algorithm works:

    Node values:       Limit:
  
        5                 10
       / \
      4   8
     /   / \
    11  13  4
   /  \      \
  7    2      1

Following the described approach:

Start at the root: Node(5). Since its value is less than the limit (10), continue the recursion. Update the limit to limit - node.value (10 - 5 = 5).
Recurse left to Node(4) and right to Node(8) with the new limit (5).
At Node(4):
- Subtract its value from the limit (5 - 4 = 1), and recurse left to Node(11) (it has no right child).
- At Node(11), subtract its value from the limit (1 - 11 = -10), which means we have surpassed our limit when we reach the children of Node(11).
- Both children of Node(11), Node(7) and Node(2), when evaluated, would result in a negative limit after subtracting their values. Thus, they will both be pruned and Node(11) will be left with no children.
- Since Node(11) is now effectively a leaf and has no sufficient subpath (its children were pruned), it is also pruned. Node(4) is left with no children.
- Node(4) becomes a leaf and is insufficient, so it is pruned.
Back at the root, recurse to the right to Node(8):
- Update the limit (5 - 8 = -3). The condition is satisfied for Node(8) since we haven't encountered a leaf. Hence, continue.
- Recurse to Node(13) and Node(4) with the new limit.
- Node(13) is a leaf. Check (-3 - 13). This is negative, which means the path of Node(8) -> Node(13) is sufficient, so we keep Node(13).
- Node(4) isn't a leaf. Update limit (-3 - 4 = -7).
  - Recurse to the right to Node(1). Node(4) has no left child.
  - Node(1) is a leaf. Check (-7 - 1), which is still negative, so the path of Node(8) -> Node(4) -> Node(1) is sufficient, and we keep Node(1).
After all recursions, the insufficient nodes have been pruned. At the end, our tree will look like:

This example demonstrates the principle of the depth-first search (DFS) algorithm in action, recursively pruning nodes that do not support paths with sums meeting or exceeding the given limit. When the recursion unwinds, the resultant tree is bereft of all insufficient nodes, and the sufficient structure is returned.

Solution Implementation

1# Class definition for a binary tree node.
2class TreeNode:
3    def __init__(self, value=0, left=None, right=None):
4        self.value = value
5        self.left = left
6        self.right = right
7
8
9class Solution:
10    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
11        """
12        Removes subtrees that are not sufficient, i.e., the total sum of any path from the root
13        to any leaf node is less than the given limit.
14      
15        :param root: TreeNode - the root of the binary tree
16        :param limit: int - the threshold limit for the sum of the path values
17        :return: TreeNode - the modified tree with insufficient subtrees removed
18        """
19      
20        # If the root node is None, just return None.
21        if root is None:
22            return None
23      
24        # Reduce the remaining limit by the value of the current node.
25        limit -= root.value
26      
27        # If it's a leaf node and the limit is not reached, prune this node.
28        if root.left is None and root.right is None:
29            return None if limit > 0 else root
30      
31        # Recursively prune the left and right subtrees.
32        root.left = self.sufficientSubset(root.left, limit)
33        root.right = self.sufficientSubset(root.right, limit)
34      
35        # If both subtrees are pruned, prune this node too.
36        return None if root.left is None and root.right is None else root
37

1/* Class definition for a binary tree node. */
2class TreeNode {
3    int val; // Value of the node
4    TreeNode left; // Pointer to the left child
5    TreeNode right; // Pointer to the right child
6
7    /* Constructor for creating a tree node without children. */
8    TreeNode(int val) {
9        this.val = val;
10    }
11
12    /* Constructor for creating a tree node with given value, left child, and right child. */
13    TreeNode(int val, TreeNode left, TreeNode right) {
14        this.val = val;
15        this.left = left;
16        this.right = right;
17    }
18}
19
20/* Solution class contains the method 'sufficientSubset' to prune the tree. */
21class Solution {
22  
23    /**
24     * Prunes the tree such that the sum of values from root to . any leaf node is at least 'limit'.
25     *
26     * @param root The root of the binary tree.
27     * @param limit The minimum sum from root to leaf required.
28     * @return The pruned binary tree.
29     */
30    public TreeNode sufficientSubset(TreeNode root, int limit) {
31        // Base case: if the current node is null, return null as there's nothing to check or prune.
32        if (root == null) {
33            return null;
34        }
35      
36        // Subtract the current node's value from the remaining limit.
37        limit -= root.val;
38      
39        // Check if the current node is a leaf node.
40        if (root.left == null && root.right == null) {
41            // If the remaining limit is still greater than 0 after considering current node's value,
42            // it means the path sum of this leaf is insufficient, hence return null (prune it).
43            // Otherwise, return the current leaf as it satisfies the condition.
44            return limit > 0 ? null : root;
45        }
46      
47        // Recursive call for the left subtree, potentially prune the left child.
48        root.left = sufficientSubset(root.left, limit);
49        // Recursive call for the right subtree, potentially prune the right child.
50        root.right = sufficientSubset(root.right, limit);
51      
52        // After the recursive calls, if both children are null, it means they were pruned, then the
53        // current node becomes a leaf and we'll need to check whether it should also be pruned or not.
54        // If at least one child remains, the current node should also remain.
55        return (root.left == null && root.right == null) ? null : root;
56    }
57}
58

1// Definition for a binary tree node.
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6  
7    // Constructor with default value initialization
8    TreeNode(int x = 0, TreeNode *left = nullptr, TreeNode *right = nullptr) 
9        : val(x), left(left), right(right) {}
10};
11
12class Solution {
13public:
14    // Function to prune the tree based on the limit provided.
15    TreeNode* sufficientSubset(TreeNode* root, int limit) {
16        // Base case: If the node is null, return null.
17        if (!root) {
18            return nullptr;
19        }
20
21        // Subtract the value of the current node from the limit.
22        limit -= root->val;
23
24        // Check if it's a leaf node.
25        if (!root->left && !root->right) {
26            // If the updated limit is greater than 0, the path sum is insufficient; prune this node.
27            return limit > 0 ? nullptr : root;
28        }
29
30        // Recursive case: Traverse down to the left and right subtrees.
31        root->left = sufficientSubset(root->left, limit);
32        root->right = sufficientSubset(root->right, limit);
33
34        // If after the pruning, the current node becomes a leaf node (i.e., both left and right are null),
35        // and the path doesn't meet the criteria, return null, else return the node itself.
36        return root->left == nullptr && root->right == nullptr ? nullptr : root;
37    }
38};
39

1// Definition for the binary tree node
2interface TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8/**
9 * Removes the subtrees where the total sum of the path from the root node to any leaf is less than the given limit.
10 * @param root - The current node of the binary tree.
11 * @param limit - The minimum required sum from the root to leaf path.
12 * @returns The modified subtree, or null if the subtree's sum is insufficient.
13 */
14function sufficientSubset(root: TreeNode | null, limit: number): TreeNode | null {
15    // Base case: if the current node is null, return null
16    if (root === null) {
17        return null;
18    }
19
20    // Subtract the value of the current node from the remaining limit
21    limit -= root.val;
22
23    // If the current node is a leaf, check if the sum of the path meets the limit
24    if (root.left === null && root.right === null) {
25        // Return null if the sum is insufficient; otherwise return the current node
26        return limit > 0 ? null : root;
27    }
28
29    // Recursively call sufficientSubset on the left and right subtrees
30    root.left = sufficientSubset(root.left, limit);
31    root.right = sufficientSubset(root.right, limit);
32
33    // If both children are removed, remove the current node as well
34    if (root.left === null && root.right === null) {
35        return null;
36    }
37
38    // Otherwise, return the current node with its potentially pruned children
39    return root;
40}
41

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(N), where N is the number of nodes in the binary tree. This is because the function visits each node exactly once in a depth-first search manner. It performs a constant amount of work at each node by subtracting the node's value from the limit and deciding whether to keep or discard the node based on the updated limit.

Space Complexity

The space complexity of the provided code is O(H), where H is the height of the binary tree. This complexity arises due to the recursive call stack that can grow up to H levels deep in the case of a skewed tree (where H can be equal to N in the worst case). For a balanced binary tree, the height H would be log(N), resulting in a space complexity of O(log(N)). However, in the worst case (such as a skewed tree), the space complexity is O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

BFS

DFS

Both

Neither

I don’t know