Check if Binary Search Tree
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-&gt;left != NULL){
        if(root-&gt;data &lt; root-&gt;left-&gt;data || !checkBST(root-&gt;left)){
            return false;
        }
    }

    if(root-&gt;right != NULL){
        if(root-&gt;data &gt; root-&gt;right-&gt;data || !checkBST(root-&gt;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 = &amp;n20;

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

// ....