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

struct node_t
{
    int value;
    struct node_t* left;
    struct node_t* right;
};

void inorder_traverse(struct node_t* node)
{
    if (node == NULL)
        return;

    inorder_traverse(node->left);
    printf(" %d ", node->value);
    inorder_traverse(node->right);
};

int check_BST(struct node_t* root)
{
    return check_BST_internal(INT_MIN, root, INT_MAX);
};

int check_BST_internal(int min, struct node_t* node, int max)
{
    if (node == NULL)
        return 1;

    if (node->value < min || node->value > max)
        return 0;

    return (check_BST_internal(min, node->left, node->value)) && (check_BST_internal(node->value, node->right, max));
};


int main()
{
    struct node_t* root_node_6 = malloc(sizeof(struct node_t));
    root_node_6->value = 6;

    struct node_t* node_3 = malloc(sizeof(struct node_t));
    node_3->value = 3;

    struct node_t* node_9 = malloc(sizeof(struct node_t));
    node_9->value = 9;

    root_node_6->left = node_3;
    root_node_6->right= node_9;

    struct node_t* node_1 = malloc(sizeof(struct node_t));
    node_1->value = 1;
    node_1->left = NULL;
    node_1->right = NULL;

    struct node_t* node_5 = malloc(sizeof(struct node_t));
    node_5->value = 2;
    node_5->left = NULL;
    node_5->right = NULL;

    node_3->left = node_1;
    node_3->right = node_5;

    struct node_t* node_7 = malloc(sizeof(struct node_t));
    node_7->value = 7;
    node_7->left = NULL;
    node_7->right = NULL;

    struct node_t* node_11 = malloc(sizeof(struct node_t));
    node_11->value = 11;
    node_11->left = NULL;
    node_11->right = NULL;

    node_9->left = node_7;
    node_9->right = node_11;

    inorder_traverse(root_node_6);

    if (check_BST(root_node_6) == 1)
        printf("\nTrue");
    else
        printf("\nFalse");


    return 0;
}