• 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