Validate Binary Search Trees

The problem asks us to validate binary search trees. We need to check if a binary tree follows BST rules.

The key insight: in-order traversal of a valid BST gives us values in sorted order. So we can traverse the tree in-order and make sure each value is greater than the previous one.

Here’s how it works:

bool isValidBST(TreeNode* root) {
    TreeNode* prev=NULL;
    return valid(root, prev);
}

bool valid(TreeNode* root, TreeNode*& prev) {
    if (root==NULL) return true;
    if (!valid(root->left, prev)) return false;
    if (prev!=NULL && prev->val>=root->val) return false;
    prev=root;
    return valid(root->right, prev);
}

The algorithm goes left first, then checks the current node, then goes right. At each step, we compare the current node with the previous one. If any current node is not greater than the previous one, we return false.

Time: O(logN) on average for tree height, O(N) in worst case Space: O(logN) for stack calls and the previous node pointer

#BST