Table of contents

Check whether a given Binary Tree is Binary Search Tree(BST) or not

Given a binary tree, write a program to check whether the tree is a binary search tree (BST) or not. A binary search tree is defined as a binary tree where for every node:

  • The values in its left subtree are less than the node's value.
  • The values in its right subtree are greater than the node's value.

Input/Output Examples

Example 1:

  • plaintext
    Input:
     2
    / \
   1   3

Output:
True
Explanation: The given binary tree is a BST because for every node, the left subtree values are smaller and the right subtree values are larger.

Example 2:
Input:
     1
    / \
   2   3

Output:
False
Explanation: The given binary tree is not a BST because 2 is in the left subtree of 1 but is greater than 1.

Approach to Check Whether a Given Binary Tree is a BST

  1. Recursive Approach with Range Limits:
    • For each node, check if it satisfies the properties of a BST by ensuring that its value is greater than the maximum value in its left subtree and less than the minimum value in its right subtree.
    • We can maintain a range (minValue and maxValue) that limits the values a node can take. Initially, the range is (-∞, ∞). As we traverse the tree, we adjust the range for each node:
      • For the left child, the maximum value allowed is the value of the current node.
      • For the right child, the minimum value allowed is the value of the current node.
  2. Base Case:
    • If the node is NULL, return True because an empty tree is a valid BST.
  3. Edge Case:
    • If a node violates the BST properties, return False.

C++ Program to Check Whether a Given Binary Tree is a BST

cpp
#include <iostream>
#include <climits>
using namespace std;

// Definition of a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// Helper function to check if the tree is a BST
bool isBSTUtil(TreeNode* node, int minValue, int maxValue) {
    // Base case: An empty tree is a BST
    if (node == NULL) {
        return true;
    }

    // Check if the current node's value is within the valid range
    if (node->data <= minValue || node->data >= maxValue) {
        return false;
    }

    // Recursively check the left and right subtrees
    return isBSTUtil(node->left, minValue, node->data) &&
           isBSTUtil(node->right, node->data, maxValue);
}

// Function to check if a binary tree is a BST
bool isBST(TreeNode* root) {
    return isBSTUtil(root, INT_MIN, INT_MAX);
}

int main() {
    // Create a sample tree
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);

    // Check if the tree is a BST
    if (isBST(root)) {
        cout << "The tree is a Binary Search Tree (BST)." << endl;
    } else {
        cout << "The tree is NOT a Binary Search Tree (BST)." << endl;
    }

    return 0;
}

Java Program to Check Whether a Given Binary Tree is a BST

java
// Definition of a binary tree node
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        data = val;
        left = right = null;
    }
}

public class CheckBST {

    // Helper function to check if the tree is a BST
    public static boolean isBSTUtil(TreeNode node, int minValue, int maxValue) {
        // Base case: An empty tree is a BST
        if (node == null) {
            return true;
        }

        // Check if the current node's value is within the valid range
        if (node.data <= minValue || node.data >= maxValue) {
            return false;
        }

        // Recursively check the left and right subtrees
        return isBSTUtil(node.left, minValue, node.data) &&
               isBSTUtil(node.right, node.data, maxValue);
    }

    // Function to check if a binary tree is a BST
    public static boolean isBST(TreeNode root) {
        return isBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    public static void main(String[] args) {
        // Create a sample tree
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        // Check if the tree is a BST
        if (isBST(root)) {
            System.out.println("The tree is a Binary Search Tree (BST).");
        } else {
            System.out.println("The tree is NOT a Binary Search Tree (BST).");
        }
    }
}

Python Program to Check Whether a Given Binary Tree is a BST

python
# Definition of a binary tree node
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Helper function to check if the tree is a BST
def is_bst_util(node, min_value, max_value):
    # Base case: An empty tree is a BST
    if node is None:
        return True

    # Check if the current node's value is within the valid range
    if node.data <= min_value or node.data >= max_value:
        return False

    # Recursively check the left and right subtrees
    return is_bst_util(node.left, min_value, node.data) and \
           is_bst_util(node.right, node.data, max_value)

# Function to check if a binary tree is a BST
def is_bst(root):
    return is_bst_util(root, float('-inf'), float('inf'))

# Example usage
if __name__ == "__main__":
    # Create a sample tree
    root = TreeNode(2)
    root.left = TreeNode(1)
    root.right = TreeNode(3)

    # Check if the tree is a BST
    if is_bst(root):
        print("The tree is a Binary Search Tree (BST).")
    else:
        print("The tree is NOT a Binary Search Tree (BST).")
  • Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited once to check if it satisfies the BST property.
  • Space Complexity: O(h), where h is the height of the tree. This space is required for the recursive call stack. In the worst case (for a skewed tree), the space complexity is O(n).

DSA

Related Articles