fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4.  
  5. /* A binary tree node has data, pointer to left child
  6.    and a pointer to right child */
  7. struct node
  8. {
  9.     int data;
  10.     struct node* left;
  11.     struct node* right;
  12. };
  13.  /* Helper function that allocates a new node with the
  14.    given data and NULL left and right pointers. */
  15. struct node* newNode(int data)
  16. {
  17.   struct node* node = (struct node*)
  18.                        malloc(sizeof(struct node));
  19.   node->data = data;
  20.   node->left = NULL;
  21.   node->right = NULL;
  22.  
  23.   return(node);
  24. }
  25.  
  26. bool isBST(struct node* root)
  27. {
  28.     static struct node *prev = NULL;
  29.  
  30.     // traverse the tree in inorder fashion and keep track of prev node
  31.     if (!root)
  32.       return true;
  33.  
  34.         if (!isBST(root->left))
  35.           return false;
  36.  
  37.         // Allows only distinct valued nodes 
  38.         if (prev != NULL && root->data <= prev->data)
  39.           return false;
  40.  
  41.         prev = root;
  42.  
  43.         return isBST(root->right);
  44.  
  45.  
  46. }
  47.  
  48. /* Driver program to test above functions*/
  49. int main()
  50. {
  51.   struct node *root = newNode(100);
  52.   root->right       = newNode(101);
  53.   root->left = newNode(4);
  54.  
  55.  
  56.   if(isBST(root))
  57.     printf("Is BST");
  58.   else
  59.     printf("Not a BST");
  60.  
  61.   getchar();
  62.   return 0;
  63. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Is BST
https://ideone.com/UDKcW9
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!