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.
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.
Which algorithm should you use to find a node that is close to the root of the tree?
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
sufficientSubsetfunction is defined withroot(the current node) andlimit(the remaining path sum before reaching insufficiency) as parameters. -
The base case for the recursion is checking if the current
rootnode isNone. If it is, we returnNone, 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 returnNoneto 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
sufficientSubseton 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
Noneafter the potential deletion of insufficient nodes. If both children areNone, we returnNone, 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).
Which algorithm should you use to find a node that is close to the root of the tree?
Example Walkthrough
Let's consider a simple binary tree alongside a limit to see how the algorithm works:
1 Node values: Limit: 2 3 5 10 4 / \ 5 4 8 6 / / \ 7 11 13 4 8 / \ \ 9 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 tolimit - node.value(10 - 5 = 5). -
Recurse left to
Node(4)and right toNode(8)with the new limit (5). -
At
Node(4):- Subtract its value from the limit (
5 - 4 = 1), and recurse left toNode(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 ofNode(11). - Both children of
Node(11),Node(7)andNode(2), when evaluated, would result in a negative limit after subtracting their values. Thus, they will both be pruned andNode(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.
- Subtract its value from the limit (
-
Back at the root, recurse to the right to
Node(8):- Update the limit (
5 - 8 = -3). The condition is satisfied forNode(8)since we haven't encountered a leaf. Hence, continue. - Recurse to
Node(13)andNode(4)with the new limit. Node(13)is a leaf. Check(-3 - 13). This is negative, which means the path ofNode(8) -> Node(13)is sufficient, so we keepNode(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 ofNode(8) -> Node(4) -> Node(1)is sufficient, and we keepNode(1).
- Recurse to the right to
- Update the limit (
-
After all recursions, the insufficient nodes have been pruned. At the end, our tree will look like:
1 5 2 \ 3 8 4 / \ 5 13 4 6 \ 7 1
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
371/* 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}
581// 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};
391// 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}
41What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Time 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.
Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.