Grokking Tree Coding Patterns for Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Insufficient Nodes in Root to Leaf Paths (medium)
On this page

Problem Statement

Examples

Try it yourself

Problem Statement

Given the root of a binary tree and an integer limit, remove all insufficient nodes from the tree, and return the root of the updated tree.

A node is insufficient if all root to leaf paths that include this node leads to a sum less than the limit. If a node is removed, all its descendants should also be removed.

A leaf is a node with no children.

Examples

Example 1:

  • Input: root = [5, 3, 8, 2, -1, null, 10], limit: 15
Image
  • Expected Output: [5, null, 8, null, 10]
  • Explanation: The initial tree has 6 nodes. The path from the root 5 -> 3 -> 2 has a sum of 10 and path from the root 5 -> 3 -> -1 has a sum 7. So, node 3 and its children will be removed.

Example 2:

  • Input: root = [5, 4, 8, 11, null, 17, 4, 7, null, null, 5, 9], limit: 22
Image
  • Expected Output: [5,4,8,11,null,17,4,7,null,null,5,9]
  • Explanation: All 3 root to leaf paths have sum greater than 22. So, we don't need to remove any nodes.

Example 3:

  • Input: root = [10, 5, 15, 2, null, null, 20, -10, null, null, 25], limit: 15
Image
  • Expected Output: [10,null,15,null,20,null,25]
  • Explanation: The path from the root to the leaf through node 5 sums to 7, which is less than 15. Therefore, node 5 and its subtree are also removed.

Constraints:

  • The number of nodes in the tree is in the range [1, 5000].
  • -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
  • -10<sup>9</sup> <= limit <= 10<sup>9</sup>

Try it yourself

Try solving this question

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Try it yourself