For the purposes of this challenge, we define a binary tree to be a binary searc
ID: 3601657 • Letter: F
Question
For the purposes of this challenge, we define a binary tree to be a binary search tree with the following ordering requirements:
The data value of every node in a node's left subtree is less than the data value of that node.
The data value of every node in a node's right subtree is greater than the data value of that node.
Given the root node of a binary tree, can you determine if it's also a binary search tree?
Complete the function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must return a boolean denoting whether or not the binary tree is a binary search tree. You may have to write one or more helper functions to complete this challenge.
/* Hidden stub code will pass a root argument to the function below. Complete the function to solve the challenge. Hint: you may want to write one or more helper functions.
The Node struct is defined as follows:
struct Node {
int data;
Node* left;
Node* right;
}
*/
bool checkBST(Node* root) {
}
Explanation / Answer
Binary Search Tree - BST:
As mentioned in the question, it is easy to understand that a binary tree - a tree with two or less children -
is also called a BST if it holds another property
- each node is greater than max of all the nodes of its left sub tree
- each node is smaller than max of all the nodes of its right sub tree
To verify, if a given binary tree is a BST or not, we should check for the above conditions recursively.
At every level we check for these conditions.
If it fails at any level, the tree is not a BST.
If the program passes through all the levels successfully, we call it a BST.
The actual conditions are to check for min and max at each node in all the levels.
For the root node, there is no condition, so the values will be INT_MIN, INT_MAX.
For the rest of the nodes, if the node is a left child of its parent, it shouldn't exceed its parent.
Thus we decide the max for its call as parent-1.
There's no special condition on its min, so it derives this value from its parent.
it the node is a right child of its parent, it shouldn't be less than its parent.
This we decide the min for its call as parent+1.
There's no special condition on its max, so it derives this value from its parent.
C++ Code :
#include <iostream>
#include <climits>
using namespace std;
/* Node - model to represent each node
It has data-an integer
Pointer to its left child - another Node
Pointer to its right child - another Node*/
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
/* This method creates a node, allocates memory for it
Copies data passed to its data variable
Initializes left and right pointers to NULL - meaning it does not
currently have any children nodes*/
struct Node* createNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
/* This method is a utility method that finds recursively
if the given tree with given root is a BST or not, including
the min and max check*/
bool isBSTMinMax(Node* root,int min, int max)
{
// If tree ends here, it can be called a BST
if (root == NULL)
return true;
// min and max boundary checks
if((root -> data < min) || (root -> data > max))
return false;
// recursion - check the same things for its left and right sub trees
// Only change is to tighten the boundaries
// For left sub tree, there's no special min condition
// But it should not be greater than or equal its parent - BST property
// So we should pass its parent-1 as max
// The same applies for right sub tree in reverse
// i.e. there's no special max, but min will be its parent+1
return isBSTMinMax(root->left, min, root->data-1) and
isBSTMinMax(root->right, root->data+1, max);
}
/* The actual method that returns if the given binary tree is a BST or not
This method uses the utilty method isBSTMinMax to find the answer
initial min and max should be defined to INT_MIN and INT_MAX as
there are no boundaries initially*/
bool isBST(Node *root){
return isBSTMinMax(root,INT_MIN,INT_MAX);
}
/*Driver method to test the above code*/
int main() {
struct Node *node = createNode(3);
node->left = createNode(1);
node->right = createNode(5);
node->left->left = createNode(0);
node->left->right = createNode(2);
if (isBST(node))
cout << "Is BST";
else
cout << "Not a BST";
return 0;
}