MediumTrees

Validate Binary Search Tree

treedfsrecursion

Problem

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both subtrees are also valid BSTs.

Examples

Example 1

Input: root = [2,1,3]

Output: true

Example 2

Input: root = [5,1,4,null,null,3,6]

Output: false

Explanation: Root is 5 but right child is 4 < 5.

Constraints

•The number of nodes is in the range [1, 10^4].
•-2^31 <= Node.val <= 2^31 - 1

Hints

Hint 1

Pass min and max bounds down the recursion — each node must be within its valid range.

Solutions

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)   // left must be < node.val
        && validate(node.right, node.val, max);  // right must be > node.val
}

Java

Time: O(n) · Space: O(h)