Validate BST

#include <bits/stdc++.h> // Includes common standard libraries (iostream, queue, limits for INT_MIN/INT_MAX)
#include "BST.h"         // Assumed to contain Node class, insertIntoBST, takeinput, levelOrderTraversal

using namespace std;     // Use the standard namespace

// Note: The Node class, insertIntoBST, takeinput, and levelOrderTraversal
// are assumed to be defined in "BST.h" for this snippet.
// For completeness, they are usually:
/*
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

Node* insertIntoBST(Node* root, int data) { ... }
void takeinput(Node* &root) { ... }
void levelOrderTraversal(Node* root) { ... }
*/

// Function to validate if a given Binary Tree is a Binary Search Tree (BST).
// This recursive function passes down a valid range [min, max] for node values.
// Time Complexity: O(N) - visits each node once.
// Space Complexity: O(H) - recursion stack space, where H is tree height.
bool ValidateBST(Node* root, int min, int max) {
    // Base Case: An empty tree (or subtree) is always a valid BST.
    if(root == NULL) {
        return true;
    }

    // Check if the current node's data is within the allowed range [min, max].
    // If it violates the range, it's not a BST.
    if(root->data >= min && root->data <= max) {
        // Recursively validate the left subtree:
        // Its new max bound becomes root->data (all left nodes must be <= root->data).
        // Its min bound remains the same.
        bool leftIsValid = ValidateBST(root->left, min, root->data);

        // Recursively validate the right subtree:
        // Its new min bound becomes root->data (all right nodes must be >= root->data).
        // Its max bound remains the same.
        bool rightIsValid = ValidateBST(root->right, root->data, max);

        // The current subtree is a valid BST ONLY if both its left and right subtrees are valid.
        return (leftIsValid && rightIsValid);
    }

    // If the current node's data violates the min/max range, it's not a BST.
    return false;
}

int main() {
    Node* root = NULL; // Initialize root of the binary tree

    cout << "Enter data to create BST (use -1 for NULL, this function builds a BST by default if BST.h is from previous example): ";
    // This takeinput function likely inserts data according to BST rules,
    // so the resulting tree should already be a BST if inputs are unique.
    // For general BST validation, you'd feed a potentially invalid binary tree.
    takeinput(root);

    cout << endl << "Level Order Traversal of the created tree : " << endl;
    levelOrderTraversal(root); // Print the tree structure

    // Validate the created tree, starting with the broadest possible range for the root.
    // INT_MIN and INT_MAX are from <limits> header.
    if(ValidateBST(root, INT_MIN, INT_MAX)) {
        cout << "YES ! It is a Binary Search Tree." << endl;
    } else {
        cout << "NO ! It is not a Binary Search Tree." << endl;
    }

    return 0;
}

/*
Example INPUT for tree creation:
(Assuming BST.h's takeinput builds a standard BST)
1. Valid BST Input:
   50 20 70 10 30 60 80 -1
   Output: YES ! It is a Binary Search Tree.

2. Invalid BST Input (This requires modifying buildTree/takeinput in BST.h
   to build an arbitrary binary tree, not strictly a BST. For example, if you
   manually create a tree like:
         50
        /  \
       70  20
   (i.e., 70 on left of 50, 20 on right of 50)
   Then ValidateBST(root, INT_MIN, INT_MAX) would return false.
   The provided `takeinput` builds a valid BST, so for `NO` output, one would
   need a custom tree builder that doesn't enforce BST rules during creation.
   However, if you input something like: `10 5 15 12 18 -1`
   Tree:
        10
       /  \
      5   15
         /  \
        12  18
   This is a valid BST.

   If you had a non-BST construction and built:
         10
        /  \
       20  5
   ValidateBST(root, INT_MIN, INT_MAX) for this would be:
   - ValidateBST(10, INT_MIN, INT_MAX)
     - 10 is in range.
     - Call left: ValidateBST(20, INT_MIN, 10) -> 20 is NOT <= 10. Returns false.
     - Result: false
   Output: NO ! It is not a Binary Search Tree.
*/

1. Binary Search Tree (BST) Properties Recap

A Binary Search Tree (BST) is defined by its ordering property:
- For every node, all values in its left subtree must be less than its own data.
- For every node, all values in its right subtree must be greater than its own data.
- Both left and right subtrees must also recursively be BSTs.
Crucial Point: It’s not just about immediate children; the property applies to all descendants in a subtree.

2. Supporting Components (Briefly)

Node class: Defines the structure of a binary tree node (data, left, right).
insertIntoBST, takeinput, levelOrderTraversal: These functions (assumed to be in BST.h) are used to create and display the binary tree which will then be validated. Note that takeinput for BST.h would typically build a valid BST. For validation, one might pass an arbitrary binary tree (not necessarily built via insertIntoBST). However, this code uses insertIntoBST for creation, implying it’s testing if the insertion process itself yields a BST. If you want to test any binary tree, takeinput should be generic, not BST-specific.

3. `ValidateBST(Node* root, int min, int max)` Function (Recursive Validation)

Purpose: Determines if a given binary tree (or subtree) adheres to all BST properties.
Core Idea: The most robust way to validate a BST is to pass down a valid range (min and max boundaries) that each node’s data must fall within. As we recurse, these bounds are tightened.
Parameters:
- Node* root: The current node being checked.
- int min: The minimum permissible value for any node in the current subtree. Values less than or equal to min are invalid.
- int max: The maximum permissible value for any node in the current subtree. Values greater than or equal to max are invalid.
Logic Flow:
1. Base Case:
  - if (root == NULL): An empty tree (or subtree) is always considered a valid BST. Return true.
2. Current Node Check:
  - if (root->data >= min && root->data <= max):
    - Check if the data of the current root node lies within the allowed min and max range inherited from its ancestors.
    - If it violates this, the entire tree is not a BST. The else part (returning false) handles this.
  - Recursive Calls (If current node is valid):
    - bool left = ValidateBST(root->left, min, root->data);
      - Recursively validate the left subtree.
      - The min bound for the left child remains the same as its parent’s min.
      - The max bound for the left child becomes root->data. This is crucial: all nodes in the left subtree must be strictly less than the current root->data. (Note: The code uses <= which means duplicates would be allowed on the left, but usually BSTs have strict < for left and > for right or a specific policy for equals. Given insertIntoBST puts duplicates on left, <= is consistent).
    - bool right = ValidateBST(root->right, root->data, max);
      - Recursively validate the right subtree.
      - The min bound for the right child becomes root->data. This is crucial: all nodes in the right subtree must be strictly greater than the current root->data.
      - The max bound for the right child remains the same as its parent’s max.
    - Combine Results: return (left && right);
      - The current subtree is a valid BST only if both its left and right subtrees are also valid BSTs.
3. Invalid Node:
  - return false;: This line is reached if root->data violates the min/max bounds, meaning the BST property is broken at this node.
Initial Call in main:
- ValidateBST(root, INT_MIN, INT_MAX): The entire tree starts with the broadest possible range. INT_MIN and INT_MAX (from <limits>) are used as initial unbounded limits.

4. Complexity Analysis for Validation

Time Complexity: O(N)
- Every node in the binary tree is visited exactly once.
Space Complexity: O(H)
- Due to the recursion call stack, where H is the height of the tree.
- Worst Case (Skewed Tree): H = N, leading to O(N) space.
- Best Case (Balanced Tree): H = log N, leading to O(log N) space.

Validate BST

1. Binary Search Tree (BST) Properties Recap

2. Supporting Components (Briefly)

3. ValidateBST(Node* root, int min, int max) Function (Recursive Validation)

4. Complexity Analysis for Validation

3. `ValidateBST(Node* root, int min, int max)` Function (Recursive Validation)