Check if Binary Search Tree

I wrote this entirely from scratch without any Googling/reading as part of an ongoing effort to improve my problem-solving skills.

Also, please note that the focus for my project was the problem solving steps rather than the code itself, which is why I have the comments. It is also why I manually set up the BST (this helped me visualize the problem in order to solve it). However, I am indeed asking for a code review.

```
#include
#include
#include
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
struct Node* parent;
} node;
bool checkBST(node *root){

//Step 1, check if the node is not null ***
//Step 2, check if left child exists
//Step 3, if left child exists, compare its data to the root/current node's data and make sure that it is SMALLER
//step 4, if the data is smaller, proceed, else return false *
//step 5, if the root's right child exists, compare its data to the root/current node's data and make sure it is BIGGER *****
//step 6, if the data is bigger, proceed, else return false ***

//step 7, recurse *
//step 8, return true *

if(root == NULL){
printf("root is null!\n");
return false;
}

if(root->left != NULL){
printf("root data: %d\nleft data: %d\n",root->data,root->left->data);
if(root->data left->data){
printf("Not a BST: left is bigger\n");
return false;
}
checkBST(root->left);
}

if(root->right != NULL){
printf("root data: %d\nright data: %d\n",root->data,root->right->data);
if(root->data > root->right->data){
printf("Not a BST: right is smaller\n");
return false;
}
checkBST(root->right);
}

return true;
}

int main(){
node n1, n2, root, n4, n5, n6;

n1 = malloc(sizeof(node));
n2 = malloc(sizeof(node));
root = malloc(sizeof(node));
n4 = m

You forgot to check the result of your recursing calls. Your steps are fine, if you meant the following in step 7


Step 7: recurse and check result

However, even then, it's not the correct property of a binary search tree. Have a look at the following tree:

5
   / \
  3   7
 / \
1   6

Does this hold for your steps? Yes. Does this hold for your algorithm, if you check the result of checkBST?

bool checkBST(node *root){
    if(root == NULL){
        return false;
    }    

    if(root->left != NULL){
        if(root->data left->data || !checkBST(root->left)){
            return false;
        }
    }

    if(root->right != NULL){
        if(root->data > root->right->data || !checkBST(root->right)){
            return false;
        }
    }

    return true;
}

Yes. But is it a binary search tree? No. You would never find 6. All nodes left of the root must be smaller, and all nodes right of the root must be greater.

Remember, a binary tree has the following property: if you want to find a value, you look at the current value. If the value you're looking for is smaller, you continue in the left tree. If the value is greater, you continue in the right tree. But you always look at one of those subtrees. Never both. In a balanced binary tree, you would only have to look at \$\log_2(N)\$ nodes to find your value.

I would link you to the Wikipedia section on Verification, but it already holds the solution. But here is a hint: carry along what numbers are allowed in your subtree.

So, to go back to your steps, you should do something like this:

• check if the node is not null

• check if left child exists

• check that all elements in the left subtree are smaller than our current value

• check if right child exists

• check that all elements in the right subtree are greater than our current value

The steps 0 and 1.5 are missing. They handle the current value and the range of valid values. Coming up with them will be the crucial part.

By the way, you usually don't use parent in a binary tree. But that depends on your use-case. Also, you have memory leaks. For small examples, there is no harm not using malloc:

struct node n10, n20, n30, n15, n50, n60;

n10.data = 10;
n10.left = NULL
n10.right = NULL
n10.parent = &n20;

n20.data   = 20;
n20.parent = &root;
n20.left   = &n10;
n20.right  = NULL;

// ....

StackExchange Code Review Q#155300, answer score: 6