medium Insufficient Nodes in Root to Leaf Paths

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

• 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

• 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

• 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⁵ <= Node.val <= 10⁵
• -10⁹ <= limit <= 10⁹

Solution

To solve this problem, we use a Depth-First Search (DFS) approach to traverse the binary tree from the root to the leaves. The main idea is to keep track of the cumulative sum of node values along each path and compare it to the given limit. If a node is part of a path where the total sum from the root to that node is less than the limit and all paths through that node lead to a sum below the limit, the node and its subtree are pruned. We recursively process both the left and right subtrees of each node. After processing, if both subtrees of a node are pruned, the node itself is pruned.

This method ensures that only the nodes that contribute to a path with a sum greater than or equal to the limit are retained in the tree. This approach is effective because it guarantees that we consider all possible root-to-leaf paths, ensuring the tree is pruned optimally based on the given limit.

Step-by-Step Algorithm

1. Define the base case:

   • Check if the current node (node) is null.
   • If node is null, return null. This handles the scenario where a subtree is empty.

2. Update the current sum:

   • Add the value of the current node (node.val) to the ongoing sum (currentSum).

3. Check if the current node is a leaf node:

   • A node is considered a leaf if both its left and right children are null.
   • If the node is a leaf, compare the updated currentSum with the limit:
     • If currentSum is less than limit, return null to prune this node.
     • If currentSum is greater than or equal to limit, return the node itself to keep it in the tree.

4. Recursively process the left subtree:

   • Call the DFS function on the left child of the current node with the updated currentSum and the given limit.
   • Assign the result of this recursive call to node.left. This will prune or keep the left subtree based on the sum.

5. Recursively process the right subtree:

   • Call the DFS function on the right child of the current node with the updated currentSum and the given limit.
   • Assign the result of this recursive call to node.right. This will prune or keep the right subtree based on the sum.

6. Check if both left and right subtrees are pruned:

   • After the recursive calls, check if both node.left and node.right are null.
   • If both are null, it means all paths from this node do not meet the limit, so return null to prune this node.

7. Return the current node:

   • If the node is not pruned, return the current node to keep it as part of the valid path in the tree.

Algorithm Walkthrough

Let’s walk through the algorithm with the example tree [5, 3, 8, 2, -1, null, 10] and a limit of 15.

• Initial Tree:

      5
     / \
    3   8
   / \   \
  2  -1  10
  

• Limit: 15

Step 1: Start DFS at the root node (5).

• Current sum: 0 + 5 = 5
• Node is not a leaf (it has children), so proceed to its subtrees.

Step 2: Process the left subtree (rooted at 3).

• Current sum: 5 + 3 = 8
• Node is not a leaf, so continue to its subtrees.

Step 3: Process the left child of 3 (node 2).

• Current sum: 8 + 2 = 10
• Node 2 is a leaf. Check if currentSum < limit.
• 10 < 15 is true, so prune node 2 by returning null.

Step 4: Process the right child of 3 (node -1).

• Current sum: 8 + (-1) = 7
• Node -1 is a leaf. Check if currentSum < limit.
• 7 < 15 is true, so prune node -1 by returning null.

Step 5: Check the node 3 after processing both children.

• Both left and right subtrees of node 3 are pruned (node.left = null, node.right = null).
• Prune node 3 by returning null.

Step 6: Process the right subtree (rooted at 8).

• Current sum: 5 + 8 = 13
• Node is not a leaf, so continue to its subtrees.

Step 7: Process the left child of 8 (which is null).

• The node is null, return null.

Step 8: Process the right child of 8 (node 10).

• Current sum: 13 + 10 = 23
• Node 10 is a leaf. Check if currentSum < limit.
• 23 >= 15 is true, so keep node 10 by returning it.

Step 9: Check the node 8 after processing both children.

• Left subtree is pruned (node.left = null).
• Right subtree is kept (node.right = node 10).
• Keep node 8 by returning it.

Step 10: Check the root node 5 after processing both subtrees.

• Left subtree is pruned (node.left = null).
• Right subtree is kept (node.right = node 8).
• Keep node 5 by returning it.

Final Pruned Tree:

  5
   \
    8
     \
     10

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     TreeNode(int val) {
//         this.val = val;
//     }
// }

public class Solution {

  public TreeNode sufficientSubset(TreeNode root, int limit) {
    return dfs(root, 0, limit);
  }

  private TreeNode dfs(TreeNode node, int currentSum, int limit) {
    if (node == null) {
      return null;
    }

    // Update the current sum by adding the node's value.
    currentSum += node.val;

    // If it's a leaf node, check if the path sum is less than the limit.
    if (node.left == null && node.right == null) {
      // If current path sum is less than the limit, return null to prune this leaf.
      return currentSum < limit ? null : node;
    }

    // Recursively prune the left and right subtrees.
    node.left = dfs(node.left, currentSum, limit);
    node.right = dfs(node.right, currentSum, limit);

    // If both children are pruned (i.e., both are null), prune this node too.
    if (node.left == null && node.right == null) {
      return null;
    }

    return node;
  }

  public void printTree(TreeNode root) {
    if (root == null) {
      System.out.println("Tree is empty");
      return;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
      int levelSize = queue.size();
      boolean hasNextLevel = false; // Flag to check if the next level has nodes
      LinkedList<String> currentLevel = new LinkedList<>(); // To store nodes of the current level

      for (int i = 0; i < levelSize; i++) {
        TreeNode current = queue.poll();

        if (current != null) {
          currentLevel.add(String.valueOf(current.val));
          // If there are children, add them to the queue
          queue.add(current.left);
          queue.add(current.right);

          // If there are any non-null children, set the flag to true
          if (current.left != null || current.right != null) {
            hasNextLevel = true;
          }
        } else {
          currentLevel.add("null");
        }
      }

      // Print the current level, excluding trailing nulls
      while (
        !currentLevel.isEmpty() && currentLevel.peekLast().equals("null")
      ) {
        currentLevel.pollLast();
      }

      for (String node : currentLevel) {
        System.out.print(node + " ");
      }

      // Stop processing if no next level exists
      if (!hasNextLevel) {
        break;
      }
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // Example 1:
    TreeNode root1 = new TreeNode(5);
    root1.left = new TreeNode(3);
    root1.right = new TreeNode(8);
    root1.left.left = new TreeNode(2);
    root1.left.right = new TreeNode(-1);
    root1.right.right = new TreeNode(10);

    int limit1 = 15;

    Solution solution = new Solution();
    TreeNode newRoot1 = solution.sufficientSubset(root1, limit1);
    System.out.print("The updated tree is: ");
    solution.printTree(newRoot1);
  }
}

Complexity Analysis

Time Complexity

The algorithm performs a depth-first search (DFS) through the binary tree, visiting each node exactly once. Therefore, the time complexity is , where N is the number of nodes in the tree. This is because each node is processed only once during the DFS traversal.

Space Complexity

The space complexity is determined by the recursion stack in the DFS. In the worst case, the space complexity will be , where H is the height of the tree. In the worst case (unbalanced tree), H can be equal to N, making the space complexity . In a balanced tree, H would be , making the space complexity .