-
Notifications
You must be signed in to change notification settings - Fork 77
/
IsBinarySearchTree.cpp
40 lines (30 loc) · 970 Bytes
/
IsBinarySearchTree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/* 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;
}
*/
#include <climits>
bool checkBST(Node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/* Returns true if the given
tree is a BST and its values
are >= min and <= max. */
int isBSTUtil(Node* node, int min, int max)
{
/* an empty tree is BST */
if (node==NULL)
return 1;
/* false if this node violates
the min/max constraint */
if (node->data < min || node->data > max)
return 0;
/* otherwise check the subtrees recursively,
tightening the min or max constraint */
return
isBSTUtil(node->left, min, node->data-1) &&
isBSTUtil(node->right, node->data+1, max);
}