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.
/*
* C++ Program to Remove All nodes which don't lie in any Path with Sum >= K
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
/*
* A Binary Tree Node
*/
struct Node
{
int data;
Node *left, *right;
};
/*
* create a new Binary Tree node with given data
*/
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
/*
* Inorder traversal.
*/
void inorder(Node *root)
{
if (root != NULL)
{
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
/*
* truncates the binary tree.
*/
Node *pruneUtil(Node *root, int k, int *sum)
{
if (root == NULL)
return NULL;
int lsum = *sum + (root->data);
int rsum = lsum;
root->left = pruneUtil(root->left, k, &lsum);
root->right = pruneUtil(root->right, k, &rsum);
*sum = max(lsum, rsum);
if (*sum < k)
{
free(root);
root = NULL;
}
return root;
}
/*
* implements pruneutil
*/
Node *prune(Node *root, int k)
{
int sum = 0;
return pruneUtil(root, k, &sum);
}
/*
* Main
*/
int main()
{
int k = 45;
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->left->left->left = newNode(8);
root->left->left->right = newNode(9);
root->left->right->left = newNode(12);
root->right->right->left = newNode(10);
root->right->right->left->right = newNode(11);
root->left->left->right->left = newNode(13);
root->left->left->right->right = newNode(14);
root->left->left->right->right->left = newNode(15);
cout<<"Tree before truncation"<<endl;
inorder(root);
root = prune(root, k);
cout<<"\nTree after truncation\n";
inorder(root);
return 0;
}
$ 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.
Related Posts:
- Practice Programming MCQs
- Check Data Structure Books
- Check Programming Books
- Check Computer Science Books
- Practice Computer Science MCQs