Home > Backend Development > C++ > C++ program to remove nodes that do not satisfy path and are greater than or equal to k

C++ program to remove nodes that do not satisfy path and are greater than or equal to k

PHPz
Release: 2023-09-14 11:25:07
forward
946 people have browsed it

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
Copy after login

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 ;
Copy after login

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;
}
Copy after login

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 
Copy after login

Our fully pruned tree -

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

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!

source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template