Back to DSA

Validate Binary Search Tree

medium
Acceptance: 42%
BSTBinary Tree

Given the root of a binary tree, determine whether it satisfies the binary search tree property. In a valid BST, every node in the left subtree has a value strictly less than the node, and every node in the right subtree has a value strictly greater than the node. This rule must hold for every node in the tree.

Examples

Example 1:
Input:root = [4,2,6]
Output:true
Example 2:
Input:root = [3,1,5,null,null,2,7]
Output:false

Hints

Related Problems

Maximum Depth of Binary TreeeasyInvert Binary TreeeasyLowest Common Ancestor of a Binary TreemediumBinary Tree Level Order TraversalmediumBinary Tree Zigzag Level Order Traversalmedium
00:00
class Solution {
    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);
    }
}
Time complexityO(n)
Space complexityO(h)