Skip to content

Instantly share code, notes, and snippets.

@ivycheung1208
Last active August 29, 2015 14:03
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save ivycheung1208/bcb725181e5a8f6035f3 to your computer and use it in GitHub Desktop.
CC150 4.5
/* 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