fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define  TreeNode node
  4.  
  5. struct node
  6. {
  7.    int val;
  8.    struct node* left;
  9.    struct node* right;
  10. };
  11.  
  12.  
  13. void del(TreeNode **child, TreeNode **par) {
  14.     if(child == NULL) return;
  15.     if((*par)->left == (*child)) {
  16.         (*par)->left = NULL;
  17.     } else {
  18.         (*par)->right = NULL;   
  19.     }
  20.     free(*(child));
  21. }
  22.  
  23. int req = 21;
  24. // code with n^2 complexity :)
  25.  
  26.  void get_ans(TreeNode **root, TreeNode **par, int sum, TreeNode **origin) {
  27.  	// never delete the root node unless u will fall in infinte recc
  28.      if((*root) == NULL || ((*origin)->left == NULL && (*origin)->right == NULL)) return;
  29.      if((*root)->left == NULL && (*root)->right == NULL) {
  30.      	// if we have a leaf node then we check for sum by including it .. of we dont get the ans
  31.      	// then we delete this leaf node and again start checking the whole tree from root
  32.      	// which is origin actually ;)
  33.      	//cout<<sum + ((*root)->val)<<"\n";
  34.          if(req != (sum + ((*root)->val))) {
  35.              del( root, par);
  36.              // after deletion we have to check tree again as tree is updated now :0
  37.              get_ans(origin, NULL, 0, origin);
  38.  
  39.          }
  40.  
  41.          return;
  42.      }
  43.      if((*root) != NULL)
  44.      get_ans(&((*root)->left), (root), sum + (*root)->val, origin);
  45.      if((*root) != NULL)
  46.      get_ans(&((*root)->right), (root), sum + (*root)->val, origin);
  47.      //return;
  48.  }
  49.  
  50.  void traverse(TreeNode **root) {
  51.      if(*root == NULL) return;
  52.      cout<<(*root)->val<<"\n";
  53.      traverse(&(*root)->left);
  54.      traverse(&(*root)->right);
  55.      return;
  56.  }
  57.  
  58. void isValidBST(TreeNode** root) {
  59.  
  60. 	TreeNode *par = NULL;
  61. 	TreeNode *ret = (*root);
  62. 	get_ans(root, &par, 0, root);
  63. 	traverse(root);
  64.  
  65. }
  66.  
  67.  
  68. struct node* newnode(int data)
  69. {
  70.   struct node* node = (struct node*)
  71.                        malloc(sizeof(struct node));
  72.   node->val = data;
  73.   node->left = NULL;
  74.   node->right = NULL;
  75.  
  76.   return(node);
  77. }
  78.  
  79. int main()
  80. {
  81.  
  82.  
  83.  
  84.   /* Constructed binary tree is
  85.             10
  86.           /   \
  87.         8      2
  88.       /  \    /
  89.     3     5  2
  90.   */
  91.   struct node *root = newnode(10);
  92.   root->left        = newnode(8);
  93.   root->right       = newnode(2);
  94.   root->left->left  = newnode(3);
  95.   root->left->right = newnode(5);
  96.   root->right->left = newnode(2);
  97.   isValidBST( &root);
  98.   return 0;
  99. }
Success #stdin #stdout 0s 2860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10
8
3
https://ideone.com/PkiFq6
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!