CC150 4.5
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* CC150 4.5 | |
* Implement a function to check if a binary tree is a binary search tree. | |
*/ | |
#include "bstree.h" // https://gist.github.com/df2d3552fbe8c2342541 | |
#include <climits> | |
using namespace std; | |
// assume duplicate value goes left | |
// Approach 1: recuisively determine whether current node is binary search tree | |
// NOT SUFFICIENT BY ONLY SATISFYING left.data <= curr.data < right.data!!! | |
// e.g. size = 7, array = [5 10 25 20 25 30 35] | |
bool isBST(Node *root) | |
{ | |
if (root == nullptr || (root->left == nullptr && root->right == nullptr)) | |
return true; // root is empty or both children are empty | |
if (root->left == nullptr) // left child is empty, check right | |
return root->right->data > root->data ? isBST(root->right) : false; | |
if (root->right == nullptr) // right child is empty, check left | |
return root->left->data <= root->data ? isBST(root->left) : false; | |
return root->left->data <= root->data && root->right->data > root->data ? | |
isBST(root->left) && isBST(root->right) : false; // both child are not empty, check both | |
} | |
// Approach 2: in-order traversal, return false when meets a value in false order | |
bool checkBST(Node *root, int &prev) | |
{ | |
if (root == nullptr) | |
return true; | |
if (!checkBST(root->left, prev)) // check left child | |
return false; | |
if (prev > root->data) // check current node | |
return false; | |
prev = root->data; // update previous value | |
if (!checkBST(root->right, prev)) // check right child | |
return false; | |
} | |
bool checkBST(Node *root) | |
{ | |
int prev = INT_MIN; | |
return checkBST(root, prev); | |
} | |
// Approach 3: reversively check left and right child, updating data range (min, max] | |
// the condition is that ALL left nodes must be less than or equal to the current node, | |
// which must be less than all the right nodes | |
bool checkBSTmm(Node *root, int min, int max) | |
{ | |
if (root == nullptr) | |
return true; | |
if (root->data <= min || root->data > max) | |
return false; | |
if (!checkBSTmm(root->left, min, root->data) || !checkBSTmm(root->right, root->data, max)) | |
return false; | |
return true; | |
} | |
bool checkBSTmm(Node *root) | |
{ | |
int min = INT_MIN; | |
int max = INT_MAX; | |
return checkBSTmm(root, min, max); | |
} | |
int main() | |
{ | |
int N; cin >> N; // input array size | |
int *arr = new int[N]; | |
for (int i = 0; i != N; ++i) | |
cin >> arr[i]; // input array data | |
bstree tree(arr, N); // the binary tree should be a BST if arr is ascending | |
cout << "Is BST? " << isBST(tree.getRoot()) << endl; // Counterexample! | |
cout << "Is BST? " << checkBST(tree.getRoot()) << endl; | |
cout << "Is BST? " << checkBSTmm(tree.getRoot()) << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment