Wednesday, August 15, 2012

Checking if a tree is a valid BST and BST Recursive Traversals


#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

typedef struct node{
int data;
struct node* left;
struct node* right;
}Node;

Node* newNode(int data){
Node* n = (Node *)malloc(sizeof(Node));
n->data = data;
n->left = NULL;
n->right = NULL;
return n;
}

void insertNode(Node* root,int data){
if(data < root->data){
if(root->left == NULL){
root->left = newNode(data);
} else {
insertNode(root->left,data);
}
} else {
if(root->right == NULL){
root->right = newNode(data);
} else {
insertNode(root->right,data);
}
}
}

Node* createBST(Node **rootRef){
Node *root = newNode(4);
insertNode(root,2);
insertNode(root,6);
insertNode(root,1);
insertNode(root,3);
insertNode(root,5);
insertNode(root,7);
*rootRef = root;
}

void inorder(Node* root){
if(root != NULL){
inorder(root->left);
printf("%d ",root->data);
inorder(root->right);
}
}

void preorder(Node* root){
if(root != NULL){
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}
}

void postorder(Node* root){
if(root != NULL){
postorder(root->left);
postorder(root->right);
printf("%d ",root->data);
}
}

int isBSTRecur(Node* root,int min,int max){
if(root == NULL){
return 1;
}
if(root->data > min && root->data < max){
return (isBSTRecur(root->left,min,root->data) && isBSTRecur(root->right,root->data,max));
} else {
return 0;
}
}

int isBST(Node* root){
return isBSTRecur(root,INT_MIN,INT_MAX);
}

int main(){
Node* root = NULL;
createBST(&root);
printf("INORDER :\n");
inorder(root);
printf("\nPREORDER :\n");
preorder(root);
printf("\nPOSTORDER :\n");
postorder(root);
if(isBST(root)){
printf("Valid BST");
} else {
printf("Invalid BST");
}
return 0;
}

No comments:

Post a Comment