Determine whether a given binary tree is a BST or not
Given a binary tree, determine whether it is a BST.
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 – 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
/ \
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’s not a BST: the value 5 is on the right subtree of the node containing 20, a violation of the BST property.
Instead of deciding based solely on a node’s values and its children, we also need information flowing down from the parent. In 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, 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, 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.
Following is the C++, Java, and Python implementation of the idea:
C++
|
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 |
#include <iostream> #include <climits> using namespace std; // Data structure to store a BST node struct Node { int data; Node* left = nullptr, *right = nullptr; Node() {} Node(int data): data(data) {} }; // Recursive function to insert a key into a BST Node* insert(Node* root, int key) { // if the root is null, create a new node and return it if (root == nullptr) { return new Node(key); } // if the given key is less than the root node, recur for the left subtree if (key < root->data) { root->left = insert(root->left, key); } // if the given key is more than the root node, recur for the right subtree else { root->right = insert(root->right, key); } return root; } // Function to determine whether a given binary tree is a BST by keeping a // valid range (starting from [-INFINITY, INFINITY]) 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 == nullptr) { return true; } // if the node's value falls outside the valid range if (node->data < minKey || node->data > maxKey) { return false; } // recursively check left and right subtrees with an updated range return isBST(node->left, minKey, node->data) && isBST(node->right, node->data, maxKey); } // Function to determine whether a given binary tree is a BST void isBST(Node* root) { if (isBST(root, INT_MIN, INT_MAX)) { printf("The tree is a BST."); } else { printf("The tree is not a BST!"); } } int main() { int keys[] = { 15, 10, 20, 8, 12, 16, 25 }; Node* root = nullptr; for (int key: keys) { root = insert(root, key); } // swap nodes swap(root->left, root->right); isBST(root); return 0; } |
Output:
The tree is not a BST!
Java
|
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 |
// A class to store a BST node class Node { int data; Node left = null, right = null; Node(int data) { this.data = data; } } class Main { // Recursive function to insert a key into a BST public static Node insert(Node root, int key) { // if the root is null, create a new node and return it if (root == null) { return new Node(key); } // if the given key is less than the root node, recur for the left subtree if (key < root.data) { root.left = insert(root.left, key); } // if the given key is more than the root node, recur for the right subtree else { root.right = insert(root.right, key); } return root; } // Function to determine whether a given binary tree is a BST by keeping a // valid range (starting from [-INFINITY, INFINITY]) and keep shrinking // it down for each node as we go down recursively public static boolean isBST(Node node, int minKey, int maxKey) { // base case if (node == null) { return true; } // if the node's value falls outside the valid range if (node.data < minKey || node.data > maxKey) { return false; } // recursively check left and right subtrees with an updated range return isBST(node.left, minKey, node.data) && isBST(node.right, node.data, maxKey); } // Function to determine whether a given binary tree is a BST public static void isBST(Node root) { if (isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE)) { System.out.println("The tree is a BST."); } else { System.out.println("The tree is not a BST!"); } } private static void swap(Node root) { Node left = root.left; root.left = root.right; root.right = left; } public static void main(String[] args) { int[] keys = { 15, 10, 20, 8, 12, 16, 25 }; Node root = null; for (int key: keys) { root = insert(root, key); } // swap left and right nodes swap(root); isBST(root); } } |
Output:
The tree is not a BST!
Python
|
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 |
import sys # A class to store a BST node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to insert a key into a BST def insert(root, key): # if the root is None, create a new node and return it if root is None: return Node(key) # if the given key is less than the root node, recur for the left subtree if key < root.data: root.left = insert(root.left, key) # if the given key is more than the root node, recur for the right subtree else: root.right = insert(root.right, key) return root # Function to determine whether a given binary tree is a BST by keeping a # valid range (starting from [-INFINITY, INFINITY]) and keep shrinking # it down for each node as we go down recursively def isBST(node, minKey, maxKey): # base case if node is None: return True # if the node's value falls outside the valid range if node.data < minKey or node.data > maxKey: return False # recursively check left and right subtrees with an updated range return isBST(node.left, minKey, node.data) and \ isBST(node.right, node.data, maxKey) # Function to determine whether a given binary tree is a BST def checkForBST(root): if isBST(root, -sys.maxsize, sys.maxsize): print('The tree is a BST.') else: print('The tree is not a BST') def swap(root): left = root.left root.left = root.right root.right = left if __name__ == '__main__': keys = [15, 10, 20, 8, 12, 16, 25] root = None for key in keys: root = insert(root, key) # swap left and right nodes swap(root) checkForBST(root) |
Output:
The tree is not a BST!
The time complexity of the above solution is O(n), where n is the size of the BST, and requires space proportional to the tree’s height for the call stack.
Another approach:
We know that an inorder traversal of a binary search tree returns the nodes in sorted order. To determine whether a given binary tree is a BST, keep track of the last visited node while traversing the tree. Then for each encountered node in the inorder traversal, check whether the last visited node is smaller (or smaller/equal, if duplicates are to be allowed in the tree) compared to the current node.
Following is the C++, Java, and Python implementation of the idea:
C++
|
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 <iostream> #include <climits> using namespace std; // Data structure to store a BST node struct Node { int data; Node* left = nullptr, *right = nullptr; Node() {} Node(int data): data(data) {} }; // Recursive function to insert a key into a BST Node* insert(Node* root, int key) { // if the root is null, create a new node and return it if (root == nullptr) { return new Node(key); } // if the given key is less than the root node, recur for the left subtree if (key < root->data) { root->left = insert(root->left, key); } // if the given key is more than the root node, recur for the right subtree else { root->right = insert(root->right, key); } return root; } // Function to perform inorder traversal on the given binary tree and // check if it is a BST or not. Here, `prev` is the previously processed node bool isBST(Node* root, Node* &prev) { // base case: empty tree is a BST if (root == nullptr) { return true; } // check if the left subtree is BST or not bool left = isBST(root->left, prev); // value of the current node should be more than that of the previous node if (root->data <= prev->data) { return false; } // update the previous node and check if the right subtree is BST or not prev = root; return left && isBST(root->right, prev); } // Function to determine whether a given binary tree is a BST void isBST(Node* node) { // pointer to store previously processed node in the inorder traversal Node* prev = new Node(INT_MIN); // check if nodes are processed in sorted order if (isBST(node, prev)) { printf("The tree is a BST."); } else { printf("The tree is not a BST!"); } } int main() { int keys[] = { 15, 10, 20, 8, 12, 16, 25 }; Node* root = nullptr; for (int key: keys) { root = insert(root, key); } // swap nodes swap(root->left, root->right); isBST(root); return 0; } |
Output:
The tree is not a BST!
Java
|
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 93 |
// A class to store a BST node class Node { int data; Node left = null, right = null; Node(int data) { this.data = data; } } class Main { // Recursive function to insert a key into a BST public static Node insert(Node root, int key) { // if the root is null, create a new node and return it if (root == null) { return new Node(key); } // if the given key is less than the root node, recur for the left subtree if (key < root.data) { root.left = insert(root.left, key); } // if the given key is more than the root node, recur for the right subtree else { root.right = insert(root.right, key); } return root; } // Function to perform inorder traversal on the given binary tree and // check if it is a BST or not. Here, `prev` is the previously processed node public static boolean isBST(Node root, Node prev) { // base case: empty tree is a BST if (root == null) { return true; } // check if the left subtree is BST or not boolean left = isBST(root.left, prev); // value of the current node should be more than that of the previous node if (root.data <= prev.data) { return false; } // update previous node data and check if the right subtree is BST or not prev.data = root.data; return left && isBST(root.right, prev); } // Function to determine whether a given binary tree is a BST public static void isBST(Node node) { // pointer to store previously processed node in the inorder traversal Node prev = new Node(Integer.MIN_VALUE); // check if nodes are processed in sorted order if (isBST(node, prev)) { System.out.println("The tree is a BST."); } else { System.out.println("The tree is not a BST!"); } } private static void swap(Node root) { Node left = root.left; root.left = root.right; root.right = left; } public static void main(String[] args) { int[] keys = { 15, 10, 20, 8, 12, 16, 25 }; Node root = null; for (int key: keys) { root = insert(root, key); } // swap nodes swap(root); isBST(root); } } |
Output:
The tree is not a BST!
Python
|
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 |
import sys # A class to store a BST node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to insert a key into a BST def insert(root, key): # if the root is None, create a new node and return it if root is None: return Node(key) # if the given key is less than the root node, recur for the left subtree if key < root.data: root.left = insert(root.left, key) # if the given key is more than the root node, recur for the right subtree else: root.right = insert(root.right, key) return root # Function to perform inorder traversal on the given binary tree and # check if it is a BST or not. Here, `prev` is the previously processed node def isBST(root, prev): # base case: empty tree is a BST if root is None: return True # check if the left subtree is BST or not left = isBST(root.left, prev) # value of the current node should be more than that of the previous node if root.data <= prev.data: return False # update previous node data and check if the right subtree is BST or not prev.data = root.data return left and isBST(root.right, prev) # Function to determine whether a given binary tree is a BST def checkForBST(node): # pointer to store previously processed node in the inorder traversal prev = Node(-sys.maxsize) # check if nodes are processed in sorted order if isBST(node, prev): print('The tree is a BST!') else: print('The tree is not a BST!') def swap(root): left = root.left root.left = root.right root.right = left if __name__ == '__main__': keys = [15, 10, 20, 8, 12, 16, 25] root = None for key in keys: root = insert(root, key) # swap nodes swap(root) checkForBST(root) |
Output:
The tree is not a BST!
The time complexity of the above solution is O(n), where n is the size of the BST, and requires space proportional to the tree’s height for the call stack.
References: https://en.wikipedia.org/wiki/Binary_search_tree
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)