recursive function that tells if a Tree is a Binary Search Tree ( BST ) (Modified code)

Question

I was working on the exercises here : "http://cslibrary.stanford.edu/110/BinaryTrees.html#s2"
I wrote a function that decides if a Tree is a BST(return 1) or not(return 0) but I'm not sure if my code is totally good, I tested it for a BST and a non-BST Tree and it seems to work correctly. I want to know the opinion of the community : Updated Code :

consider the Tree ( not a BST ) :

     5  
    / \ 
   2   7 
  / \ 
 1   6

my Idea is to compare 2 with 5 if it's good, then 1 with 5, and if it's good then 6 with 5 if it's good then 1 with 2 if it's good then 6 with 2 if it's good then 5 with 7 ; if it's good isBST() returns 1. this code is supposed to do it recursively.

the node structure :

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

the code :

int lisgood(struct node* n1,struct node* n2)
{
    if(n2 == NULL)
        return 1;
    else{
    int r = lisgood(n1,n2->left)*lisgood(n1,n2->right);
        if(r){
            if(n1->data >= n2->data)
            {
                return r;
            }
            else return 0;
        }
        else return r;
    }
}
int risgood(struct node* n1,struct node* n2)
{
    if(n2 == NULL)
        return 1;
    else{
        int r = risgood(n1,n2->right)*risgood(n1,n2->left);
        if(r){
            if(n1->data < n2->data)
            {
                return r;
            }
            else return 0;
        }
        else return r;
    }
}

int isBST(struct node* node)
{
    if(node == NULL)
        return 1;
    else{
        if(lisgood(node,node->left)&&risgood(node,node->right)){
            return (isBST(node->left)&&isBST(node->right));
        }
        else return 0;
    }
}

Answer 1

Your code doesn't really work - not even for the example you showed. You never compare 5 to 6. Basically you are comparing the root of a sub-tree with root->left, root->left->left, root->left->left->left, etc. Then you are comparing root with root->right, root->right->right, etc., but you never compare root with the other nodes in the subtree. The problem is that you don't compare a tree's root with every element on its right and left subtrees, and you should.

This is a known interview question. The simpler way to solve it is to pass in the minimum and maximum values allowed for a sub-tree as parameters.

Here's how it works with the example tree you showed: you see 5, thus, the maximum value for any node on 5's left subtree is 5. Similarly, the minimum value for any node on 5's right subtree is 5. This property is applied recursively to check that every node's value is consistent with the requirements. Here's a working implementation (assumes a tree with no duplicates):

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

struct tree_node {
    int key;
    struct tree_node *left;
    struct tree_node *right;
};

static int is_bst_aux(struct tree_node *root, int min, int max) {
    if (root == NULL) {
        return 1;
    }

    if (!(min < root->key && root->key < max)) {
        return 0;
    }

    if (!is_bst_aux(root->left, min, root->key)) {
        return 0;
    }

    return is_bst_aux(root->right, root->key, max);
}

int is_bst(struct tree_node *root) {
    return is_bst_aux(root, INT_MIN, INT_MAX);
}