Insufficient Nodes in Root to Leaf Paths — Solution
Insufficient Nodes in Root to Leaf Paths solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Insufficient Nodes in Root to Leaf Paths is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary tree and an integer limit.
A node is insufficient if every root-to-leaf path that passes through it has a sum of values strictly smaller than limit. (A leaf is a node with no children.)
Delete all insufficient nodes at the same time and return the root of the resulting tree. If the root itself is insufficient, the result is the empty tree [].
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]
Explanation: Every path through a -99 sums below 1, so those nodes go; the paths 1→2→4→8, 1→2→4→9 and 1→3→7→14 reach at least 1 and stay.
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]
Explanation: The leaf 1 (path sum 21) and the leaf 3 (path sum 20) fall short of 22 and are removed; every other node lies on a path summing to at least 22.
Example 3
Input: root = [1,2,-3,-5,null,4], limit = -1
Output: [1,null,-3,4]
Explanation: The only path through 2 is 1 + 2 - 5 = -2 < -1, so 2 and -5 go; the path 1 - 3 + 4 = 2 keeps 1, -3 and 4.
Constraints
1 <= number of nodes <= 5000-10^5 <= Node.val <= 10^5-10^9 <= limit <= 10^9
Hints for Insufficient Nodes in Root to Leaf Paths
Hint 1
Whether a node survives depends on the best root-to-leaf path through it — so on the sum above it and the best sum below it.
Hint 2
Walk down carrying the sum from the root. At a leaf you know the full path sum and can decide on the spot.
Hint 3
An inner node survives exactly when at least one of its children survived after pruning; if neither did, every path through it was too small.
How to solve Insufficient Nodes in Root to Leaf Paths
Prune bottom-up. A leaf is kept when its full path sum reaches limit; an inner node is kept when any child is kept, because a kept child carries a path through the node that is long enough.
Approach
- Walk depth-first from the root, passing down the sum of the values above the current node.
- Add the node's value. If it is a leaf, return it if the sum is at least
limit, otherwise return null. - Otherwise replace each existing child by the result of pruning it with the new sum.
- Return the node if it still has a child, otherwise null.
- The pruned root (possibly null) is the answer.
Why it works
The root-to-leaf paths through an inner node are exactly the paths through its children, extended by the same prefix. So the node has a sufficient path if and only if one of its children does — which is what keeping the node iff a child survived checks. A node with only one child has no path through the missing side, so that side must not count as a leaf.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- A node with one child is not a leaf: do not judge it by the path ending at it.
- Decide inner nodes after their children are pruned — a node whose children all disappear must disappear too.
- Path sums fit in 32 bits here (5000 · 10^5), but compare with
>= limit, not>.
Reference solution
Python
from typing import Optional
def sufficientSubset(root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
def prune(node, s):
s += node.val
if node.left is None and node.right is None:
return node if s >= limit else None
if node.left:
node.left = prune(node.left, s)
if node.right:
node.right = prune(node.right, s)
return node if node.left or node.right else None
return prune(root, 0) if root else NoneJava
public static TreeNode sufficientSubset(TreeNode root, int limit) {
return root == null ? null : pruneWalk(root, 0, limit);
}
static TreeNode pruneWalk(TreeNode node, int s, int limit) {
s += node.val;
if (node.left == null && node.right == null) return s >= limit ? node : null;
if (node.left != null) node.left = pruneWalk(node.left, s, limit);
if (node.right != null) node.right = pruneWalk(node.right, s, limit);
return node.left != null || node.right != null ? node : null;
}C++
TreeNode* pruneWalk(TreeNode* node, int s, int limit);
TreeNode* sufficientSubset(TreeNode* root, int limit) {
return root ? pruneWalk(root, 0, limit) : nullptr;
}
TreeNode* pruneWalk(TreeNode* node, int s, int limit) {
s += node->val;
if (!node->left && !node->right) return s >= limit ? node : nullptr;
if (node->left) node->left = pruneWalk(node->left, s, limit);
if (node->right) node->right = pruneWalk(node->right, s, limit);
return (node->left || node->right) ? node : nullptr;
}JavaScript
var sufficientSubset = function(root, limit) {
return root === null ? null : pruneWalk(root, 0, limit);
};
var pruneWalk = function(node, s, limit) {
s += node.val;
if (node.left === null && node.right === null) return s >= limit ? node : null;
if (node.left !== null) node.left = pruneWalk(node.left, s, limit);
if (node.right !== null) node.right = pruneWalk(node.right, s, limit);
return node.left !== null || node.right !== null ? node : null;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals