Remove nodes with path sum less than K
Filed under Amazon
Free read 1 of 3Confirm if the path sum is evaluated strictly from root to leaf, and if internal nodes with no valid child paths should also be removed.
The question
Given a binary tree and an integer K, remove all nodes whose path sum from the root to any leaf is less than K. A node is removed if it does not lie on any path from root to leaf whose sum is >= K.
Constraints
- The number of nodes in the tree is in the range [1, 10^4].
- -1000 <= Node.val <= 1000
- -10^9 <= K <= 10^9
Examples
- Input
- root = [1,2,3,4,-5,null,4], K = 5
- Output
- [1,3,4]
- Why
- Paths with sums: 1->2->4 = 7 (>=5), 1->2->-5 = -2 (<5, remove), 1->3->4 = 8 (>=5). Node 2 loses its right child. Node -5 and its parent branch are pruned.
Approach
Confirm if the path sum is evaluated strictly from root to leaf, and if internal nodes with no valid child paths should also be removed.
Calculate all root-to-leaf sums first, mark valid nodes, and perform a second pass to delete invalid ones.
Use post-order traversal recursively. As we return from children, subtract current node value from remaining sum (or pass accumulated sum down), and return null if both subtrees become invalid and the current node is not part of a valid path.
Empty tree (root is null), or tree with negative values where sums fluctuate.
Tips
- What they are testing: Test trees where all paths sum to less than K (should return None/null) and single-node trees.
- Common mistake: Failing to handle leaf nodes correctly during bottom-up backtracking or missing parent pointer updates when children are pruned.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.