fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // A utility function to get maximum of two integers
  5. int max(int l, int r) { return (l > r ? l : r); }
  6.  
  7. // A Binary Tree Node
  8. struct Node
  9. {
  10.     int data;
  11.     struct Node *left, *right;
  12. };
  13.  
  14. // A utility function to create a new Binary Tree node with given data
  15. struct Node* newNode(int data)
  16. {
  17.     struct Node* node = (struct Node*) malloc(sizeof(struct Node));
  18.     node->data = data;
  19.     node->left = node->right = NULL;
  20.     return node;
  21. }
  22.  
  23. // print the tree in LVR (Inorder traversal) way.
  24. void print(struct Node *root)
  25. {
  26.     if (root != NULL)
  27.     {
  28.         print(root->left);
  29.         printf("%d ",root->data);
  30.         print(root->right);
  31.     }
  32. }
  33.  
  34. /* Main function which truncates the binary tree. */
  35. void pruneUtil(struct Node *root, int k, int *sum)
  36. {
  37.     // Base Case
  38.     if (root == NULL)  return;
  39.  
  40.     *sum+=root->data;
  41.  
  42.  if(root->left==NULL&&root->right==NULL)
  43.  {
  44.  	if(*sum<k)
  45.  	{
  46.  	//	while(root->right==NULL)
  47.  		//{
  48.  			*sum-=root->data;
  49.  			free(root);
  50.  			root=NULL;
  51.  		//}
  52.  	}
  53.  }
  54.      pruneUtil(root->left, k, sum);
  55.      pruneUtil(root->right, k, sum);
  56.  
  57.  
  58. }
  59.  
  60. // A wrapper over pruneUtil()
  61. void prune(struct Node *root, int k)
  62. {
  63.     int sum = 0;
  64.     pruneUtil(root, k, &sum);
  65. }
  66.  
  67. // Driver program to test above function
  68. int main()
  69. {
  70.     int k = 45;
  71.     struct Node *root = newNode(1);
  72.     root->left = newNode(2);
  73.     root->right = newNode(3);
  74.     root->left->left = newNode(4);
  75.     root->left->right = newNode(5);
  76.     root->right->left = newNode(6);
  77.     root->right->right = newNode(7);
  78.     root->left->left->left = newNode(8);
  79.     root->left->left->right = newNode(9);
  80.     root->left->right->left = newNode(12);
  81.     root->right->right->left = newNode(10);
  82.     root->right->right->left->right = newNode(11);
  83.     root->left->left->right->left = newNode(13);
  84.     root->left->left->right->right = newNode(14);
  85.     root->left->left->right->right->left = newNode(15);
  86.  
  87.     printf("Tree before truncation\n");
  88.     print(root);
  89.  
  90.      prune(root, k); // k is 45
  91.  
  92.     printf("\n\nTree after truncation\n");
  93.     print(root);
  94.  
  95.     return 0;
  96. }
  97.  
Runtime error #stdin #stdout 0s 3428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Cz6Z7P
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!