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. }

$ 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
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.