Check for BST (DSA)

Problem Statement:(👈click here for GFG)

Given the root of a binary tree. Check whether it is a BST or not.

Note: We are considering that BSTs can not contain duplicate Nodes.
A BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

 

Example 1:

Input:
   2
 /    \
1      3
Output: 1 
Explanation: 
The left subtree of root node contains node
with key lesser than the root nodes key and 
the right subtree of root node contains node 
with key greater than the root nodes key.
Hence, the tree is a BST.

Example 2:

Input:
  2
   \
    7
     \
      6
       \
        5
         \
          9
           \
            2
             \
              6
Output: 0 
Explanation: 
Since the node with value 7 has right subtree 
nodes with keys less than 7, this is not a BST.

Your Task:
You don't need to read input or print anything. Your task is to complete the function isBST() which takes the root of the tree as a parameter and returns true if the given binary tree is BST, else returns false. 

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the BST).

Constraints:
0 <= Number of edges <= 100000

Solution:

Approach:

The given code checks whether a binary tree is a Binary Search Tree (BST) or not. The function isBST(root) takes the root of the binary tree as input and returns a boolean value indicating whether it is a valid BST or not. The function isBSTUtil(root, min, max) is a helper function that performs the actual check.

The helper function isBSTUtil() takes three arguments: root, min, and max. root is the current node being processed, and min and max are the minimum and maximum values that a node's data can take to satisfy the BST property. Initially, min is set to -Infinity, and max is set to Infinity. This is because there are no bounds on the data of the root node.

The isBSTUtil() function then checks if the current node violates the BST property. If the current node's data is less than or equal to min or greater than or equal to max, it violates the BST property, and the function returns false.

If the current node does not violate the BST property, the function recursively checks the left and right subtrees. For the left subtree, the min value remains the same, but the max value is updated to the current node's data, as all nodes in the left subtree must have values less than the current node. Similarly, for the right subtree, the max value remains the same, but the min value is updated to the current node's data, as all nodes in the right subtree must have values greater than the current node.

Finally, if both the left and right subtrees are valid BSTs, the function returns true.

function isBST(root) {

    //initially max and min values can be considered as Infinity and -Infinity.

    return isBSTUtil(root, -Infinity, Infinity);

}

function isBSTUtil(root, min, max) {

    //base case.

    if (root === null)

        return true;

    //checking if the current node violates the BST property.

    if (root.data <= min || root.data >= max)

        return false;

    //recursively checking for left and right subtrees.

    return isBSTUtil(root.left, min, root.data) && 

        isBSTUtil(root.right, root.data, max);

}

Another snipet:

class Solution 

{

    //Function to check whether a Binary Tree is BST or not.

    isBST(root)

    {

        //your code here

         //initially max and min values can be considered as Infinity and -Infinity.

        return this.isBSTUtil(root, -Infinity, Infinity);

    }

     isBSTUtil(root, min, max) {

        //base case.

        if (root === null)

            return true;

        //checking if the current node violates the BST property.

        if (root.data <= min || root.data >= max)

            return false;

        //recursively checking for left and right subtrees.

        return this.isBSTUtil(root.left, min, root.data) && 

            this.isBSTUtil(root.right, root.data, max);

    }

}

Thank you,

Learning is a never-ending process, and every day is an opportunity to learn something new. Keep exploring, keep pushing your limits, and keep striving towards your goals. Remember that every small step counts, and even the smallest progress is worth celebrating. Don't be afraid to ask questions, seek guidance, and learn from others. With dedication and hard work, you can achieve anything you set your mind to. So keep learning, keep growing, and keep shining!