Insufficient Nodes in Root to Leaf Paths

Medium
1940.

Insufficient Nodes in Root to Leaf Paths

Insufficient Nodes in Root to Leaf Paths is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} limit
 * @return {TreeNode}
 */
var sufficientSubset = function(root, limit) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. 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.

  2. 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.

  3. 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

  1. Walk depth-first from the root, passing down the sum of the values above the current node.
  2. Add the node's value. If it is a leaf, return it if the sum is at least limit, otherwise return null.
  3. Otherwise replace each existing child by the result of pruning it with the new sum.
  4. Return the node if it still has a child, otherwise null.
  5. 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 None

Java

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