1. What is a Binary Search Tree?

A Binary Search Tree (BST) is a type of binary tree where:

• For every node:
  • All nodes in the left subtree have values less than the node’s value.
  • All nodes in the right subtree have values greater than the node’s value.
• Both the left and right subtrees must themselves also be BSTs.

Example of a valid BST:

      10
     /  \
    5   15
       /  \
     12   20

Example of an invalid BST:

      10
     /  \
    5    8   ← 8 is less than 10 but in the right subtree

2. What Does It Mean to Validate a BST?

Validation means checking whether a binary tree obeys the BST property.

A common mistake is to check only that:

node.left.val < node.val && node.right.val > node.val

But this is not enough. We must ensure that all nodes in the left and right subtrees satisfy the conditions recursively.

3. Common Mistakes

• Only comparing immediate children.
• Not checking the full valid range of values in subtrees.
• Not handling Integer.MIN_VALUE and Integer.MAX_VALUE edge cases correctly.

4. Approaches to Validate a BST

Approach 1: Inorder Traversal Method

Idea: An in-order traversal of a BST yields a sorted (increasing) sequence. So, if we traverse in-order and keep track of the previous node, we can check whether the current node’s value is greater than the previous.

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class BSTValidator {

    private TreeNode prev = null;

    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }

    private boolean inorder(TreeNode node) {
        if (node == null) return true;

        if (!inorder(node.left)) return false;

        if (prev != null && node.val <= prev.val) return false;

        prev = node;

        return inorder(node.right);
    }
}

Time Complexity:

• O(n): Each node is visited once.

Space Complexity:

• O(h): Recursion stack, where h is the height of the tree.

Approach 2: Recursive Min-Max (Range-based)

Idea: For each node, pass down a valid range:

• All nodes in the left subtree must be < node.val
• All nodes in the right subtree must be > node.val

public class BSTValidator {

    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(TreeNode node, long min, long max) {
        if (node == null) return true;

        if (node.val <= min || node.val >= max) return false;

        return validate(node.left, min, node.val) &&
               validate(node.right, node.val, max);
    }
}

Why Use long?

To handle extreme values like Integer.MIN_VALUE and Integer.MAX_VALUE.

Time Complexity:

• O(n): Each node is checked once.

Space Complexity:

• O(h): Recursion stack.

Approach 3: Iterative Range-based (Using Stack)

Idea: Same as min-max method, but use an explicit stack to avoid recursion.

import java.util.*;

class BSTValidator {

    static class NodeBound {
        TreeNode node;
        long min, max;

        NodeBound(TreeNode node, long min, long max) {
            this.node = node;
            this.min = min;
            this.max = max;
        }
    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        Deque<NodeBound> stack = new ArrayDeque<>();
        stack.push(new NodeBound(root, Long.MIN_VALUE, Long.MAX_VALUE));

        while (!stack.isEmpty()) {
            NodeBound current = stack.pop();
            TreeNode node = current.node;

            if (node.val <= current.min || node.val >= current.max)
                return false;

            if (node.right != null)
                stack.push(new NodeBound(node.right, node.val, current.max));

            if (node.left != null)
                stack.push(new NodeBound(node.left, current.min, node.val));
        }

        return true;
    }
}