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.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
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.
Next Steps:
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Apply for Data Structure Internship
- Apply for Computer Science Internship
- Buy Programming Books
- Apply for Information Technology Internship
- Buy Computer Science Books