C Program to Check if a Tree is Binary Search Tree

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.

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.

If you find any mistake above, kindly email to [email protected]

« Prev - Circular Singly Linked List in C

» Next - C Program to Check Expression is Correctly Parenthesized

Related Posts:

Recommended Articles: