Check for BST

Time: O(n)

Space: O(h)

Intuition

Pass valid range [min, max] down the tree. Each node must be strictly within (min, max). Left child has max=current.val; right child has min=current.val.

Algorithm

1IsValidBST(node, min, max):
2If node is null, return true.
3If node.val <= min or node.val >= max, return false.
4Return IsValidBST(left, min, node.val) && IsValidBST(right, node.val, max).

Example Walkthrough

Input: root = [2,1,3]

1.Node 2: range (âˆ’âˆž,+âˆž) âœ“. Node 1: range (âˆ’âˆž,2) âœ“. Node 3: range (2,+âˆž) âœ“.

Output: true

Common Pitfalls

•Use long.MinValue/MaxValue (or null) as initial bounds â€” int bounds fail on equal-value edge cases.

Check for BST.java

Java

// Approach: DFS with valid range [min, max]. For each node verify min < node.val < max.
// Update range: left child gets [min, node.val], right child gets [node.val, max].
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {
    // Function to check whether a Binary Tree is BST or not.
    boolean isBST(Node root) {
        int min = Integer.MIN_VALUE;
        int max = Integer.MAX_VALUE;
        return checkBST(root, min, max);
    }

    boolean checkBST(Node root, int min, int max) {
        if (root == null)
            return true;

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

        boolean left = checkBST(root.left, min, root.data);
        boolean right = checkBST(root.right, root.data, max);

        return left && right;
    }
}

Was this solution helpful?