C++ Program to Remove All nodes which don’t lie in any Path with Sum >= K

«
»
This C++ Program demonstrates the Removal of All the nodes which don’t lie in any Path with Sum greater than or equal to K.

Here is source code of the C++ Program to Remove All the nodes which don’t lie in any Path with Sum >= K. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* 
  2.  * C++ Program to Remove All nodes which don't lie in any Path with Sum >= K
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <algorithm>
  8. using namespace std; 
  9. /* 
  10.  * A Binary Tree Node
  11.  */
  12. struct Node
  13. {
  14.     int data;
  15.     Node *left, *right;
  16. };
  17. /* 
  18.  * create a new Binary Tree node with given data
  19.  */ 
  20. Node* newNode(int data)
  21. {
  22.     Node* node = new Node;
  23.     node->data = data;
  24.     node->left = node->right = NULL;
  25.     return node;
  26. }
  27. /* 
  28.  * Inorder traversal.
  29.  */  
  30. void inorder(Node *root)
  31. {
  32.     if (root != NULL)
  33.     {
  34.         inorder(root->left);
  35.         cout<<root->data<<"  ";
  36.         inorder(root->right);
  37.     }
  38. }
  39.  
  40. /* 
  41.  * truncates the binary tree. 
  42.  */
  43. Node *pruneUtil(Node *root, int k, int *sum)
  44. {
  45.     if (root == NULL)  
  46.         return NULL;
  47.     int lsum = *sum + (root->data);
  48.     int rsum = lsum;
  49.     root->left = pruneUtil(root->left, k, &lsum);
  50.     root->right = pruneUtil(root->right, k, &rsum);
  51.     *sum = max(lsum, rsum);
  52.     if (*sum < k)
  53.     {
  54.         free(root);
  55.         root = NULL;
  56.     }
  57.     return root;
  58. }
  59. /* 
  60.  * implements pruneutil
  61.  */
  62. Node *prune(Node *root, int k)
  63. {
  64.     int sum = 0;
  65.     return pruneUtil(root, k, &sum);
  66. }
  67.  
  68. /* 
  69.  * Main
  70.  */
  71. int main()
  72. {
  73.     int k = 45;
  74.     Node *root = newNode(1);
  75.     root->left = newNode(2);
  76.     root->right = newNode(3);
  77.     root->left->left = newNode(4);
  78.     root->left->right = newNode(5);
  79.     root->right->left = newNode(6);
  80.     root->right->right = newNode(7);
  81.     root->left->left->left = newNode(8);
  82.     root->left->left->right = newNode(9);
  83.     root->left->right->left = newNode(12);
  84.     root->right->right->left = newNode(10);
  85.     root->right->right->left->right = newNode(11);
  86.     root->left->left->right->left = newNode(13);
  87.     root->left->left->right->right = newNode(14);
  88.     root->left->left->right->right->left = newNode(15);
  89.     cout<<"Tree before truncation"<<endl;
  90.     inorder(root);
  91.     root = prune(root, k);
  92.     cout<<"\nTree after truncation\n";
  93.     inorder(root);
  94.     return 0;
  95. }

advertisement
$ g++ remove_nodes.cpp
$ a.out
 
Tree before truncation
8  4  13  9  15  14  2  12  5  1  6  3  10  11  7
Tree after truncation
4  9  15  14  2  1
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn