Check for BST

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.

Examples:

Input:
   2
 /    \
1      3
        \
         5
Output: true 
Explanation: 
The left subtree of every node contains smaller keys and right subtree of every node contains greater. Hence, the tree is a BST.

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

Input:
   10
 /    \
5      20
      /   \
     9     25
Output: false
Explanation: The node is present in the right subtree of 10, but it is smaller than 10.

Expected Time Complexity: O(n) 
Expected Auxiliary Space: O(Height of the tree)
where n is the number of nodes in the given tree

Constraints:
1 ≤ Number of nodes ≤ 10⁵
1 ≤ Data of a node ≤ 10⁵

Approach 01

#include <limits.h>

class Solution {
public:
    // Function to check whether a Binary Tree is BST or not.
    bool isBST(Node* root) {
        // If the tree is empty, it's considered a BST.
        if (root == NULL) {
            return true;
        }
        // Use helper function to validate the BST property with initial min and max values.
        return isBSTUtil(root, INT_MIN, INT_MAX);
    }

private:
    // Helper function to check the BST property for each node.
    bool isBSTUtil(Node* node, int minValue, int maxValue) {
        // Base case: An empty tree is a BST.
        if (node == NULL) {
            return true;
        }
        // Check if the current node's data is within the valid range.
        if (node->data <= minValue) {
            return false;
        }
        if (node->data >= maxValue) {
            return false;
        }
        // Recursively check the left and right subtrees with updated ranges.
        return isBSTUtil(node->left, minValue, node->data) && isBSTUtil(node->right, node->data, maxValue);
    }
};

class Solution:
    # Function to check whether a Binary Tree is BST or not.
    def isBST(self, root):
        # If the tree is empty, it's considered a BST.
        if root is None:
            return True
        # Use helper function to validate the BST property with initial min and max values.
        return self.isBSTUtil(root, float('-inf'), float('inf'))

    # Helper function to check the BST property for each node.
    def isBSTUtil(self, node, minValue, maxValue):
        # Base case: An empty tree is a BST.
        if node is None:
            return True
        # Check if the current node's data is within the valid range.
        if node.data <= minValue:
            return False
        if node.data >= maxValue:
            return False
        # Recursively check the left and right subtrees with updated ranges.
        return self.isBSTUtil(node.left, minValue, node.data) and self.isBSTUtil(node.right, node.data, maxValue)

Time Complexity

• Traversing the Tree:

  The algorithm checks each node of the tree exactly once. Therefore, the time complexity is \( O(n) \), where \( n \) is the number of nodes in the binary tree.

• Helper Function Calls:

  The helper function isBSTUtil is called recursively for each node, ensuring that every node is visited and checked against the BST property constraints.

• Overall Time Complexity:

  The overall time complexity is \( O(n) \), where \( n \) is the number of nodes in the binary tree.

Space Complexity

• Auxiliary Space:

  The auxiliary space is mainly due to the recursion stack. In the worst case, the depth of the recursion stack can be equal to the height of the tree.

• Worst Case (Skewed Tree):

  In the worst case, the height of the tree is \( O(n) \) (e.g., a skewed tree), so the space complexity in this scenario would be \( O(n) \).

• Best Case (Balanced Tree):

  In the best case, the height of the tree is \( O(\log n) \) (e.g., a balanced tree), so the space complexity in this scenario would be \( O(\log n) \).

• Overall Space Complexity:

  The overall space complexity is \( O(h) \), where \( h \) is the height of the tree. This can be \( O(n) \) in the worst case and \( O(\log n) \) in the best case.