Jobs

Interviews

Discussions

Insufficient Nodes in Root to Leaf Paths

Medium

Asked by:

16 views

Topics:

TreesRecursion

Given the root of a binary tree and an integer limit, delete all insufficient nodes in the tree simultaneously, and return the root of the resulting binary tree.

A node is insufficient if every root to leaf path intersecting this node has a sum strictly less than limit.

A leaf is a node with no children.

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]

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]

Example 3:

Input: root = [1,2,-3,-5,null,4,null], limit = -1
Output: [1,null,-3,4]

Constraints:

The number of nodes in the tree is in the range [1, 5000].
-10⁵ <= Node.val <= 10⁵
-10⁹ <= limit <= 10⁹

Try coding it in LeetCode

Insufficient Nodes in Root to Leaf Paths

Medium

Asked by:

16 views

Topics:

TreesRecursion

Given the root of a binary tree and an integer limit, delete all insufficient nodes in the tree simultaneously, and return the root of the resulting binary tree.

A node is insufficient if every root to leaf path intersecting this node has a sum strictly less than limit.

A leaf is a node with no children.

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]

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]

Example 3:

Input: root = [1,2,-3,-5,null,4,null], limit = -1
Output: [1,null,-3,4]

Constraints:

The number of nodes in the tree is in the range [1, 5000].
-10⁵ <= Node.val <= 10⁵
-10⁹ <= limit <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the tree? Can they be negative, zero, or floating-point numbers?
What constitutes 'insufficient'? Is the limit inclusive or exclusive?
If a node has only one child and the path from the root to that child is insufficient, should that node be removed, or should the insufficient path be considered as going through that single child?
If all nodes are removed, should I return null or an empty tree (a single null node)?
Are we guaranteed that the root node is not null?

Brute Force Solution

Approach

The brute force method in this tree problem involves exploring every possible path from the root to a leaf. For each path, we check if it meets a certain requirement, and if it doesn't, we try to remove the nodes causing the failure.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree, the root.
Trace every single path from the root all the way down to the very bottom leaves.
For each of these paths, calculate a total value, like the sum of all the numbers along the path.
Compare this total value to a given minimum value.
If the total value is less than the minimum value, we need to cut out parts of the path to fix it.
Try cutting out the very last node on the path (the leaf). See if that helps.
If that doesn't help, try cutting out the node before the last one. See if that makes the total value big enough.
Keep trying to cut out nodes, one at a time, working your way back up the path from the leaf towards the root, until either the total value is good enough, or you've removed too much of the path.
If you have a choice of cutting either the left side or the right side of a branch, try both and see which one gives the best result according to the path's value in comparison to the limit.
Once you've checked and possibly trimmed every single path, return the tree with all the insufficient nodes removed.

Code Implementation

def insufficient_nodes_brute_force(root, limit):
    def get_all_paths(node, current_path):
        if not node:
            return []

        current_path = current_path + [node]

        if not node.left and not node.right:
            return [current_path]

        all_paths = []
        all_paths.extend(get_all_paths(node.left, current_path))
        all_paths.extend(get_all_paths(node.right, current_path))
        return all_paths

    all_paths = get_all_paths(root, [])

    nodes_to_remove = set()

    for path in all_paths:
        path_sum = sum(node.val for node in path)

        if path_sum < limit:
            # If the path sum is insufficient, mark nodes for removal.
            for node in path:
                nodes_to_remove.add(node)

    def remove_insufficient_nodes(node):
        if not node:
            return None

        if node in nodes_to_remove:
            return None

        node.left = remove_insufficient_nodes(node.left)

        # Recursively remove insufficient right nodes
        node.right = remove_insufficient_nodes(node.right)

        return node

    root = remove_insufficient_nodes(root)

    # Return the modified tree
    return root

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm explores every root-to-leaf path in the tree. In the worst case, the tree is highly unbalanced, resembling a linked list with n nodes. For each path (which could have length n), it potentially iterates backward from the leaf towards the root to remove insufficient nodes. This backward iteration, in the worst-case scenario, takes O(n) time. Since there can be up to n such paths in the worst-case, the overall time complexity becomes O(n * n), thus O(n^2).

Space Complexity

O(H) – The dominant space complexity stems from the recursive calls made during the depth-first traversal of the tree. In the worst-case scenario, the recursion depth can reach the height (H) of the tree. Each recursive call adds a new frame to the call stack, storing information such as local variables and the return address. Therefore, the auxiliary space used is proportional to the height of the tree, resulting in O(H) space complexity. In a balanced tree, H would be log(N), and in a skewed tree, H would be N, where N is the number of nodes.

Optimal Solution

Approach

The goal is to prune nodes from a tree where every path from the root to a leaf has a sum less than a given limit. We use a method that looks at each part of the tree and decides whether to keep it based on the sum of the path leading to it, working from the top down.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree (the root).
As you go down each path, keep track of the running sum from the root to the current point.
When you get to a leaf (the end of a path), check if the total sum of the path is at least the given limit.
If the sum is less than the limit, that means this leaf and everything above it on this particular path are 'insufficient'.
Go back up the tree. If a node only has 'insufficient' children (meaning all paths going through it are too small), then that node is also 'insufficient' and should be removed.
Repeat this process, removing insufficient nodes, until you can't remove any more.
If the root of the tree becomes 'insufficient' through this process, then the entire tree is insufficient and you return nothing, indicating that the original tree should be discarded; otherwise, you return the modified tree.

Code Implementation

def sufficient_node(root, current_sum, limit):
    if not root:
        return None

    current_sum += root.val

    # Check if the current node is a leaf.
    if not root.left and not root.right:
        return root if current_sum >= limit else None

    # Recursively process left and right subtrees.
    root.left = sufficient_node(root.left, current_sum, limit)
    root.right = sufficient_node(root.right, current_sum, limit)

    # Prune the current node if both children are insufficient.
    if not root.left and not root.right:
        return None

    return root

def prune_insufficient_nodes(root, limit):
    # Kick off the recursive pruning process.
    root = sufficient_node(root, 0, limit)

    # If the root is pruned, return None.
    return root

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses the tree in a depth-first manner, visiting each node once. The crucial operation is calculating the path sum from the root to each node. The 'limit' comparison at each leaf node and the subsequent removal of insufficient nodes are all performed within this single traversal. Therefore, the time complexity is directly proportional to the number of nodes (n) in the tree, resulting in O(n) time complexity.

Space Complexity

O(H) – The algorithm's space complexity is primarily determined by the recursion depth. In the worst-case scenario, the tree could be highly unbalanced, resembling a linked list, resulting in a recursion depth of H, where H is the height of the tree. Each recursive call consumes stack space, leading to O(H) auxiliary space. In the best case (a balanced tree), H would be log(N), where N is the number of nodes, but in the worst case, H can be N. Therefore, the space complexity is O(H).

Edge Cases

Case	How to Handle
Null or empty tree	Return null immediately as there are no paths to evaluate.
Single node tree	Check if the node's value is less than the limit; if so, return null, otherwise return the node.
All node values are negative, and limit is positive	The entire tree will be pruned except for nodes close to the root which exceed limit.
All node values are zero, and limit is positive	The entire tree will be pruned as no path will sum up to equal or exceed the limit.
Tree with very deep branches	Ensure the recursive solution handles deep trees without causing a stack overflow; consider iterative solution.
Tree with a wide branching factor at each node	The algorithm should efficiently handle numerous child nodes without excessive memory usage.
Integer overflow in path sum	Use long data type, or check path sums to avoid overflow during calculation.
Limit is extremely large positive number	No nodes will be pruned unless they have negative values bringing the path below limit.

Null or empty tree

How to Handle:

Return null immediately as there are no paths to evaluate.

Single node tree

How to Handle:

Check if the node's value is less than the limit; if so, return null, otherwise return the node.

All node values are negative, and limit is positive

How to Handle:

The entire tree will be pruned except for nodes close to the root which exceed limit.

All node values are zero, and limit is positive

How to Handle:

The entire tree will be pruned as no path will sum up to equal or exceed the limit.

Tree with very deep branches

How to Handle:

Ensure the recursive solution handles deep trees without causing a stack overflow; consider iterative solution.

Tree with a wide branching factor at each node

How to Handle:

The algorithm should efficiently handle numerous child nodes without excessive memory usage.

Integer overflow in path sum

How to Handle:

Use long data type, or check path sums to avoid overflow during calculation.

Limit is extremely large positive number

How to Handle:

No nodes will be pruned unless they have negative values bringing the path below limit.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the tree? Can they be negative, zero, or floating-point numbers?
What constitutes 'insufficient'? Is the limit inclusive or exclusive?
If a node has only one child and the path from the root to that child is insufficient, should that node be removed, or should the insufficient path be considered as going through that single child?
If all nodes are removed, should I return null or an empty tree (a single null node)?
Are we guaranteed that the root node is not null?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree, the root.
Trace every single path from the root all the way down to the very bottom leaves.
For each of these paths, calculate a total value, like the sum of all the numbers along the path.
Compare this total value to a given minimum value.
If the total value is less than the minimum value, we need to cut out parts of the path to fix it.
Try cutting out the very last node on the path (the leaf). See if that helps.
If that doesn't help, try cutting out the node before the last one. See if that makes the total value big enough.
Keep trying to cut out nodes, one at a time, working your way back up the path from the leaf towards the root, until either the total value is good enough, or you've removed too much of the path.
If you have a choice of cutting either the left side or the right side of a branch, try both and see which one gives the best result according to the path's value in comparison to the limit.
Once you've checked and possibly trimmed every single path, return the tree with all the insufficient nodes removed.

Code Implementation

def insufficient_nodes_brute_force(root, limit):
    def get_all_paths(node, current_path):
        if not node:
            return []

        current_path = current_path + [node]

        if not node.left and not node.right:
            return [current_path]

        all_paths = []
        all_paths.extend(get_all_paths(node.left, current_path))
        all_paths.extend(get_all_paths(node.right, current_path))
        return all_paths

    all_paths = get_all_paths(root, [])

    nodes_to_remove = set()

    for path in all_paths:
        path_sum = sum(node.val for node in path)

        if path_sum < limit:
            # If the path sum is insufficient, mark nodes for removal.
            for node in path:
                nodes_to_remove.add(node)

    def remove_insufficient_nodes(node):
        if not node:
            return None

        if node in nodes_to_remove:
            return None

        node.left = remove_insufficient_nodes(node.left)

        # Recursively remove insufficient right nodes
        node.right = remove_insufficient_nodes(node.right)

        return node

    root = remove_insufficient_nodes(root)

    # Return the modified tree
    return root

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree (the root).
As you go down each path, keep track of the running sum from the root to the current point.
When you get to a leaf (the end of a path), check if the total sum of the path is at least the given limit.
If the sum is less than the limit, that means this leaf and everything above it on this particular path are 'insufficient'.
Go back up the tree. If a node only has 'insufficient' children (meaning all paths going through it are too small), then that node is also 'insufficient' and should be removed.
Repeat this process, removing insufficient nodes, until you can't remove any more.
If the root of the tree becomes 'insufficient' through this process, then the entire tree is insufficient and you return nothing, indicating that the original tree should be discarded; otherwise, you return the modified tree.

Code Implementation

def sufficient_node(root, current_sum, limit):
    if not root:
        return None

    current_sum += root.val

    # Check if the current node is a leaf.
    if not root.left and not root.right:
        return root if current_sum >= limit else None

    # Recursively process left and right subtrees.
    root.left = sufficient_node(root.left, current_sum, limit)
    root.right = sufficient_node(root.right, current_sum, limit)

    # Prune the current node if both children are insufficient.
    if not root.left and not root.right:
        return None

    return root

def prune_insufficient_nodes(root, limit):
    # Kick off the recursive pruning process.
    root = sufficient_node(root, 0, limit)

    # If the root is pruned, return None.
    return root

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty tree	Return null immediately as there are no paths to evaluate.
Single node tree	Check if the node's value is less than the limit; if so, return null, otherwise return the node.
All node values are negative, and limit is positive	The entire tree will be pruned except for nodes close to the root which exceed limit.
All node values are zero, and limit is positive	The entire tree will be pruned as no path will sum up to equal or exceed the limit.
Tree with very deep branches	Ensure the recursive solution handles deep trees without causing a stack overflow; consider iterative solution.
Tree with a wide branching factor at each node	The algorithm should efficiently handle numerous child nodes without excessive memory usage.
Integer overflow in path sum	Use long data type, or check path sums to avoid overflow during calculation.
Limit is extremely large positive number	No nodes will be pruned unless they have negative values bringing the path below limit.

Null or empty tree

How to Handle:

Return null immediately as there are no paths to evaluate.

Single node tree

How to Handle:

Check if the node's value is less than the limit; if so, return null, otherwise return the node.

All node values are negative, and limit is positive

How to Handle:

The entire tree will be pruned except for nodes close to the root which exceed limit.

All node values are zero, and limit is positive

How to Handle:

The entire tree will be pruned as no path will sum up to equal or exceed the limit.

Tree with very deep branches

How to Handle:

Ensure the recursive solution handles deep trees without causing a stack overflow; consider iterative solution.

Tree with a wide branching factor at each node

How to Handle:

The algorithm should efficiently handle numerous child nodes without excessive memory usage.

Integer overflow in path sum

How to Handle:

Use long data type, or check path sums to avoid overflow during calculation.

Limit is extremely large positive number

How to Handle:

No nodes will be pruned unless they have negative values bringing the path below limit.