Use C++ to delete all nodes that are not on any path and the path sum is less than k

In this problem, we have a binary tree whose path from root node to leaf node is fully defined. The sum of all nodes from the root node to the leaf nodes must be greater than or equal to k. So we need to delete all nodes in the path whose sum is less than k. The important thing to remember here is that a node may be part of many paths, so such nodes are removed only if the sum of all paths

From the root node to the leaf nodes, we can calculate the sum. When the recursive call to the node completes and control returns, we can check if the sum of the left and right paths

Suppose we have 150 K and a tree like this -

      10
      / \
     20 30
    / \  / \
   5 35 40 45
   / \ / \
  50 55 60 65
  / \    / /
  70 80 90 100

If we see that the sum of the path root->left->left is 10 20 5, which is 25, which is less than 150, We need to prune it and remove 5. After that, let's evaluate 10->30->40. It's less than 150, so delete 40. Now we see another path 10->20->35->50, the sum of 115 is less than 150, so we delete 50. Now we are left with paths that are

10->20->35->55->70 ;
10->20->35->55->80 ;
10->30->45->60->90 ;
10->30->45->65->100 ;

The sum of all paths is greater than 150, so we don't need to prune anymore.

Example

#include <iostream>
using namespace std;
class Node {
   public:
   int value;
   Node *left, *right;
   Node(int value) {
      this->value = value;
      left = right = NULL;
   }
};
Node* removeNodesWithPathSumLessThanK(Node* root, int k, int& sum) {
   if(root == NULL) return NULL;
   int leftSum, rightSum;
   leftSum = rightSum = sum + root->value;
   root->left = removeNodesWithPathSumLessThanK(root->left, k, leftSum);
   root->right = removeNodesWithPathSumLessThanK(root->right, k, rightSum);
   sum = max(leftSum, rightSum);
   if(sum < k) {
      free(root);
      root = NULL;
   }
   return root;
}
void printInorderTree(Node* root) {
   if(root) {
      printInorderTree(root->left);
      cout << root->value << " ";
      printInorderTree(root->right);
   }
}
int main() {
   int k = 150;
   Node* root = new Node(10);
   root->left = new Node(20);
   root->right = new Node(30);
   root->left->left = new Node(5);
   root->left->right = new Node(35);
   root->right->left = new Node(40);
   root->right->right = new Node(45);
   root->left->right->left = new Node(50);
   root->left->right->right = new Node(55);
   root->right->right->left = new Node(60);
   root->right->right->right = new Node(65);
   root->left->right->right->left = new Node(70);
   root->left->right->right->right = new Node(80);
   root->right->right->left->left = new Node(90);
   root->right->right->right->left = new Node(100);
   int sum = 0;
   cout << "Inorder tree before: ";
   printInorderTree(root);
   root = removeNodesWithPathSumLessThanK(root, k, sum);
   cout << "\nInorder tree after: ";
   printInorderTree(root);
   return 0;
}

Output

Inorder tree before: 5 20 50 35 70 55 80 10 40 30 90 60 45 100 65
Inorder tree after: 20 35 70 55 80 10 30 90 60 45 100 65

Our fully pruned tree -

         10
         / \
      20 30
      \   \
      35 45
       \ / \
    55  60 65
    / \  /  /
  70 80 90 100

Conclusion

As we can see, After the initial observation, we can apply DFS and remove nodes by calculating the sum of that node as the recursive function returns from each call. Overall, this is a simple matter of observation and methodology.

The above is the detailed content of Use C++ to delete all nodes that are not on any path and the path sum is less than k. For more information, please follow other related articles on the PHP Chinese website!