Data Structures and Algorithms (SEMTZC363) - Assignment – 2 – PS9
---->DSA Group 19
[Link] SHWETA AJAYKUMAR KIRANDEVI (2022MT70138)
[Link] KITTUR (2022MT70229)
[Link] KHAN (2022MT70203)
[Link] VENKATA SAI KEERTHI (2022MT70156)
Write a program that takes in a potentially invalid Binary search tree (BST) and returns a Boolean
representing whether the BST is valid. Each BST node has an integer value, a left child node, and a
right child node. A node is said to be a valid BST node if and only if it satisfies the BST property: its
value is strictly greater than the values of every node to its left; its value is less than or equal to the
values of every node to its right; and its children’s nodes are either valid BST nodes themselves or
None/null. A BST is valid if and only if all of its nodes are valid BST nodes.
CODE:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h> // for INT_MIN, INT_MAX
struct Node {
int value;
struct Node* left;
struct Node* right;
};
//Function to check if a BST is valid
bool isValidBSTHelper(struct Node* node, int min, int max) {
if (node == NULL) {
return true;
}
if (node->value <= min || node->value > max) {
return false;
return isValidBSTHelper(node->left, min, node->value) && isValidBSTHelper(node->right, node-
>value, max);
bool isValidBST(struct Node* root) {
return isValidBSTHelper(root, INT_MIN, INT_MAX);
int main() {
struct Node* root = (struct Node*)malloc(sizeof(struct Node));
root->value = 10;
root->left = (struct Node*)malloc(sizeof(struct Node));
root->left->value = 5;
root->left->left = (struct Node*)malloc(sizeof(struct Node));
root->left->left->value = 2;
root->left->left->left = (struct Node*)malloc(sizeof(struct Node));
root->left->left->left->value = 1;
root->left->left->left->left = NULL;
root->left->left->left->right = NULL;
root->left->right = (struct Node*)malloc(sizeof(struct Node));
root->left->right->value = 5;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (struct Node*)malloc(sizeof(struct Node));
root->right->value = 15;
root->right->left = (struct Node*)malloc(sizeof(struct Node));
root->right->left->value = 13;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (struct Node*)malloc(sizeof(struct Node));
root->right->right->value = 22;
root->right->right->left = NULL;
root->right->right->right = (struct Node*)malloc(sizeof(struct Node));
root->right->right->right->value = 14;
root->right->right->right->left = NULL;
root->right->right->right->right = NULL;
bool isValid = isValidBST(root);
if (isValid) {
printf("True\n");
} else {
printf("False\n");
// Free memory
free(root->left->left->left);
free(root->left->left);
free(root->left->right);
free(root->left);
free(root->right->left);
free(root->right->right->right);
free(root->right->right);
free(root->right);
free(root);
return 0;
OUTPUT FOR BELOW CODE:
