Check if Binary Search Tree

Question

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 <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
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 < root->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 = malloc(sizeof(node));
    n5 = malloc(sizeof(node));
    n6 = malloc(sizeof(node));

    //Set up data values
    n1->data = 10;
    n2->data = 20;
    root->data = 30;
    n4->data = 15; //modified this node to test for negative outcome
    n5->data = 50;
    n6->data = 60;

    //Set up children/parents
    root->parent = NULL;
    root->left = n2;
    root->right = n4;
    n1->left = NULL;
    n1->right = NULL;
    n2->parent = root;
    n2->left = n1;
    n2->right = NULL;
    n4->parent = root;
    n4->left = NULL;
    n4->right = n5;
    n5->parent = n4;
    n5->left = NULL;
    n5->right = n6;
    n6->parent = n5;
    n6->left = NULL;
    n6->right = NULL;


if(checkBST(root) == true){
    printf("This is a BST!");
}

    return(EXIT_SUCCESS);
}

Answer 1

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 < root->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:

1. check if the node is not null
2. check if left child exists
   • check that all elements in the left subtree are smaller than our current value
3. 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;

// ....

Answer 2

You can check whether the tree is a binary search tree by traversing the tree in-order and making sure that the data keys in nodes are increasing:

static node* min(node* node_)
{
    while (node_->left)
    {
        node_ = node_->left;
    }

    return node_;
}

static node* successor(node* node_)
{
    if (node_->right)
    {
        return min(node_->right);
    }

    node* node_parent_ = node_->parent;

    while (node_parent_ && node_parent_->right == node_)
    {
        node_ = node_parent_;
        node_parent_ = node_parent_->parent;
    }

    return node_parent_;
}

bool coderodde_check_bst(node* root)
{
    node* node_ = min(root);
    int current_data = node_->data;

    while ((node_ = successor(node_)))
    {
        if (current_data >= node_->data)
        {
            return false;
        }

        current_data = node_->data;
    }

    return true;
}

You may think that this is \$\Theta(n \log n)\$, but it is, in fact, \$\Theta(n)\$, since you spend constant time in each tree node, and you visit each node at most 3 times: once from parent, once from the left child and once from the right child.