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);
}