Insufficient Nodes in Root to Leaf Paths

MediumTreesdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

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 less than limit. (A leaf is a node with no children.) Delete all insufficient nodes at the same time, together with their subtrees, and return the root of what remains. If the root itself is insufficient, return an empty tree. The result is graded in level order. Deletion never creates a new leaf whose paths fall short: a node that survives always keeps at least one child on a path reaching limit.

Examples

Input: root = [1,2,-3,-5,null,4], limit = -1
Output: [1,null,-3,4]
Path 1 -> 2 -> -5 sums to -2, so 2 and -5 are insufficient. Path 1 -> -3 -> 4 sums to 2 and survives.
Input: root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 26
Output: [5,4,8,11,null,17,null,7]
Sums are 27, 21, 30, 22 and 20. Only the paths ending at 7 and 17 reach 26, so 1, the lower 4, 5 and 3 are removed.
Input: root = [1,2,3], limit = 10
Output: []
No path reaches 10, so even the root is deleted.

Constraints

  • 1 <= number of nodes <= 5000
  • -10^5 <= Node.val <= 10^5
  • -10^9 <= limit <= 10^9

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems