#include<bits/stdc++.h>
using namespace std;
#define TreeNode node
struct node
{
int val;
struct node* left;
struct node* right;
};
void del(TreeNode **child, TreeNode **par) {
if(child == NULL) return;
if((*par)->left == (*child)) {
(*par)->left = NULL;
} else {
(*par)->right = NULL;
}
free(*(child));
}
int req = 21;
// code with n^2 complexity :)
void get_ans(TreeNode **root, TreeNode **par, int sum, TreeNode **origin) {
// never delete the root node unless u will fall in infinte recc
if((*root) == NULL || ((*origin)->left == NULL && (*origin)->right == NULL)) return;
if((*root)->left == NULL && (*root)->right == NULL) {
// if we have a leaf node then we check for sum by including it .. of we dont get the ans
// then we delete this leaf node and again start checking the whole tree from root
// which is origin actually ;)
//cout<<sum + ((*root)->val)<<"\n";
if(req != (sum + ((*root)->val))) {
del( root, par);
// after deletion we have to check tree again as tree is updated now :0
get_ans(origin, NULL, 0, origin);
}
return;
}
if((*root) != NULL)
get_ans(&((*root)->left), (root), sum + (*root)->val, origin);
if((*root) != NULL)
get_ans(&((*root)->right), (root), sum + (*root)->val, origin);
//return;
}
void traverse(TreeNode **root) {
if(*root == NULL) return;
cout<<(*root)->val<<"\n";
traverse(&(*root)->left);
traverse(&(*root)->right);
return;
}
void isValidBST(TreeNode** root) {
TreeNode *par = NULL;
TreeNode *ret = (*root);
get_ans(root, &par, 0, root);
traverse(root);
}
struct node* newnode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->val = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
/* Constructed binary tree is
10
/ \
8 2
/ \ /
3 5 2
*/
struct node *root = newnode(10);
root->left = newnode(8);
root->right = newnode(2);
root->left->left = newnode(3);
root->left->right = newnode(5);
root->right->left = newnode(2);
isValidBST( &root);
return 0;
}