This C Program Checks whether a Tree is a Binary Search Tree.
Here is source code of the C program to Check whether a Tree is a Binary Search Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
/*
* C Program to Check whether a Tree is a Binary Search Tree
*/
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
static struct node *prev = NULL;
/*Function to check whether the tree is BST or not*/
int is_bst(struct node* root)
{
if (root)
{
if (!is_bst(root->left)) //moves towards the leftmost child of the tree and checks for the BST
return 0;
if (prev != NULL && root->data <= prev->data)
return 0;
prev = root;
return is_bst(root->right); //moves the corresponding right child of the tree and checks for the BST
}
return 1;
}
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()
{
/*
The input tree is as shown below
40
/ \
20 60
/ \ \
10 30 80
\
90
*/
struct node *root = newNode(40);
root->left = newNode(20);
root->right = newNode(60);
root->left->left = newNode(10);
root->left->right = newNode(30);
root->right->right = newNode(80);
root->right->right->right = newNode(90);
if (is_bst(root))
printf("TREE 1 Is BST");
else
printf("TREE 1 Not a BST");
prev = NULL;
/*
The input tree is as shown below
50
/ \
20 30
/ \
70 80
/ \ \
10 40 60
*/
struct node *root1 = newNode(50);
root1->left = newNode(20);
root1->right = newNode(30);
root1->left->left = newNode(70);
root1->left->right = newNode(80);
root1->left->left->right = newNode(40);
root1->left->left->leftt = newNode(90);
if (is_bst1(root1))
printf("TREE 2 Is BST");
else
printf("TREE 2 Not a BST");
return 0;
}
$ cc tree8.c $ a.out TREE 1 Is BST TREE 2 Not a BST
Sanfoundry Global Education & Learning Series – 1000 C Programs.
advertisement
Here’s the list of Best Books in C Programming, Data-Structures and Algorithms
If you wish to look at programming examples on all topics, go to C Programming Examples.
Related Posts:
- Check Programming Books
- Check Data Structure Books
- Check Computer Science Books
- Practice Programming MCQs
- Practice Design & Analysis of Algorithms MCQ