Question

/* * struct for a single node in a binary tree. data contains the int

* stored in this node. left and right contain pointers to the left and

* right subtrees respectively. *

* All of the ints stored in the left subtree is smaller than data.

* All of the ints stored in the right subtree is larger than data.

*/

struct node {

int data;

struct node *left;

struct node *right;

};

typedef struct node node;

Write a recursive function treeTrim which deletes all of the tree nodes on level n or lower. current contains the current level. The function returns a pointer to the node that the parent of tree should now point to (this will be either tree or NULL node* treeTrim(node «tree, int n, int current) ( W1 Write the previous function without passing the current level (hint: you need to change n when going down levels) node, treeTrin(node "tree, int n)t

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct node
{
int data;
struct node* left;
struct node* right;
};

int isBSTUtil(struct node* node, int min, int max);
int isBST(struct node* node)
{
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
int isBSTUtil(struct node* node, int min, int max)
{
if (node==NULL)
return 1;
if (node->data < min || node->data > max)
return 0;
return
isBSTUtil(node->left, min, node->data-1) && // Allow only distinct values
isBSTUtil(node->right, node->data+1, max); // Allow only distinct values
}

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}
int main()
{
struct node *root = newNode(4);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(3);

if(isBST(root))
printf("Is BST");
else
printf("Not a BST");

getchar();
return 0;
}

using NULL pointers
#include <bits/stdc++.h>
using namespace std;

struct Node
{
int data;
struct Node* left, *right;
};
bool isBST(Node* root, Node* l=NULL, Node* r=NULL)
{
// Base condition
if (root == NULL)
return true;
if (l != NULL and root->data < l->data)
return false;
if (r != NULL and root->data > r->data)
return false;
return isBST(root->left, l, root) and
isBST(root->right, root, r);
}

struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main()
{
struct Node *root = newNode(3);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(4);

if (isBST(root))
cout << "Is BST";
else
cout << "Not a BST";

return 0;
}