Given a Binary Tree, figure out whether it’s a Binary Search Tree. In a binary search tree, each node’s key value is smaller than the key value of all nodes in the right subtree, and are greater than the key values of all nodes in the left subtree i.e. L < N < RL<N<R.
Below is an example of binary tree that is a valid BST.
Below is an example of a binary tree that is not a BST
bool is_bst_rec( BinaryTreeNode* root, int min_value, int max_value) { if (root == nullptr) { return true; } if (root->data < min_value || root->data > max_value) { return false; } return is_bst_rec(root->left, min_value, root->data) && is_bst_rec(root->right, root->data, max_value); } bool is_bst(BinaryTreeNode* root) { return is_bst_rec( root, numeric_limits<int>::min(), numeric_limits<int>::max()); } void test_is_bst() { BinaryTreeNode* root = create_random_BST(15); BinaryTreeNode* root2 = create_BinaryTree(20); root2->left = root; root2->right = root; display_level_order(root); display_level_order(root2); assert(is_bst(root)); assert(!is_bst(root2)); } int main(int argc, char* argv[]) { test_is_bst(); }
The runtime complexity of this solution is linear, O(n).
The memory complexity of this solution is linear, O(n).
There are several ways of solving this problem. A basic algorithm would be to check on each node where the maximum value of its left sub-tree is less than the node’s data and the minimum value of its right sub-tree is greater than the node’s data. This is highly inefficient as for each node, both of its left and right sub-trees are explored.
Another approach would be to do a regular in-order traversal and in each recursive call, pass maximum and minimum bounds to check whether the current node’s value is within the given bounds. This approach is efficient compared to the one above.