C++ program to remove nodes that do not satisfy path and are greater than or equal to 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 the constant value k. Therefore, we need to remove all nodes in those paths whose sum is less than k, so that the remaining paths in the tree will be greater than k. The important thing to remember here is that a node may be part of many paths, so such nodes are only removed if the sum of all paths leading to that node

From the root node to the leaf node, 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, less than 150, we need to prune it and remove 5. After that, let's evaluate 10->30->40. It is less than 150, so 40 is deleted.

Now we see another path 10->20->35->50, the sum of 115 is less than 150, so we delete 50. Now our remaining path is

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

The following is a C program that demonstrates how to delete nodes that are not in any path and whose sum is greater than or equal to any constant value k -

#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

in 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 C++ program to remove nodes that do not satisfy path and are greater than or equal to k. For more information, please follow other related articles on the PHP Chinese website!