Given a Binary Tree, determine if it is a BST or not.

This problem has a simple recursive solution. The BST property “*every node on the right subtree has to be larger than the current node and every node on the left subtree has to be smaller than the current node*” is the key to figuring out whether a tree is a BST or not.

The greedy algorithm – simply traverse the tree, at every node check whether the node contains a value larger than the value at the left child and smaller than the value on the right child – does not work for all cases. Consider the following tree:

20

/ \

10 30

/ \

5 40

In the tree above, each node meets the condition that the node contains a value larger than its left child and smaller than its right child hold, and yet it is not a BST: the value 5 is on the right subtree of the node containing 20, a violation of the BST property.

Instead of making a decision based solely on the values of a node and its children, we also need information flowing down from the parent as well. In the case of the tree above, if we could remember about the node containing the value 20, we would see that the node with value 5 is violating the BST property contract.

So the condition we need to check at each node is:

- if the node is the left child of its parent, then it must be smaller than (or equal to) the parent and it must pass down the value from its parent to its right subtree to make sure none of the nodes in that subtree is greater than the parent
- if the node is the right child of its parent, then it must be larger than the parent and it must pass down the value from its parent to its left subtree to make sure none of the nodes in that subtree is lesser than the parent.

**C++ implementation –**

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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <bits/stdc++.h> using namespace std; // Data structure to store a Binary Search Tree node struct Node { int data; Node *left, *right; }; // Function to create a new binary tree node having given key Node* newNode(int key) { Node* node = new Node; node->data = key; node->left = node->right = nullptr; return node; } // Function to perform inorder traversal of the tree void inorder(Node* root) { if (root == nullptr) return; inorder(root->left); cout << root->data << " "; inorder(root->right); } // Recursive function to insert an key into BST Node* insert(Node* root, int key) { // if the root is null, create a new node an return it if (root == nullptr) return newNode(key); // if given key is less than the root node, recuse for left subtree if (key < root->data) root->left = insert(root->left, key); // if given key is more than the root node, recuse for right subtree else root->right = insert(root->right, key); return root; } // Function to determine if given Binary Tree is a BST or not by keeping a // valid range (starting from [MIN_VALUE, MAX_VALUE]) and keep shrinking // it down for each node as we go down recursively bool isBST(Node* node, int minKey, int maxKey) { // base case if (node == NULL) return true; // if node's value fall outside valid range if (node->data < minKey || node->data > maxKey) return false; // recursively check left and right subtrees with updated range return isBST(node->left, minKey, node->data) && isBST(node->right, node->data, maxKey); } // Function to determine if given Binary Tree is a BST or not void isBST(Node* root) { if(isBST(root, INT_MIN, INT_MAX)) printf("This is a BST."); else printf("This is NOT a BST!"); } // main function int main() { Node* root = nullptr; int keys[] = { 15, 10, 20, 8, 12, 16, 25 }; for (int key : keys) root = insert(root, key); // swap nodes swap(root->left, root->right); isBST(root); return 0; } |

**Output: **

This is NOT a BST!

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

**Another approach: **

We know that an in-order traversal of a binary search tree returns the nodes in sorted order. Thus, to determine if given binary tree is BST or not, we can perform in-order traversal and keep track of the last visited node while traversing the tree and check whether its key is smaller (or smaller/equal, if duplicates are to be allowed in the tree) compared to the current key.

**C++ implementation –**

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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include <bits/stdc++.h> using namespace std; // Data structure to store a Binary Search Tree node struct Node { int data; Node *left, *right; }; // Function to create a new binary tree node having given key Node* newNode(int key) { Node* node = new Node; node->data = key; node->left = node->right = nullptr; return node; } // Recursive function to insert an key into BST Node* insert(Node* root, int key) { // if the root is null, create a new node an return it if (root == nullptr) return newNode(key); // if given key is less than the root node, recuse for left subtree if (key < root->data) root->left = insert(root->left, key); // if given key is more than the root node, recuse for right subtree else root->right = insert(root->right, key); return root; } // Function to perform inorder traversal of the given binary tree and // check if it is a BST or not. Here prev is previous processed node bool isBST(Node* root, Node* &prev) { // base case: empty tree is a BST if (root == nullptr) return true; // check if left subtree is BST or not bool left = isBST(root->left, prev); // value of current node should be more than that of previous node if (root->data <= prev->data) return false; // update previous node and check if right subtree is BST or not prev = root; return left && isBST(root->right, prev); } // Function to determine if given Binary Tree is a BST or not void isBST(Node* node) { // pointer to store previous processed node in inorder traversal Node* prev = newNode(INT_MIN); // check if nodes are nodes are processed in sorted order if (isBST(node, prev)) printf("This is a BST."); else printf("This is NOT a BST!"); } // main function int main() { Node* root = nullptr; int keys[] = { 15, 10, 20, 8, 12, 16, 25 }; for (int key : keys) root = insert(root, key); // swap nodes swap(root->left, root->right); isBST(root); return 0; } |

**Output: **

This is NOT a BST!

The time complexity of above solution is O(n).

**References:**

https://en.wikipedia.org/wiki/Binary_search_tree

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply