Validate Binary Search Tree

Problem

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

A valid BST is defined as follows:

• 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 the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

• The number of nodes in the tree is in the range [1, 10<sup>4</sup>].

• -2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1

Solution

Idea: We need to use the property of the binary search tree, where the left child is less than the parent, and the parent is less than the right child. This rule must apply to all ancestors and descendants. In other words, any left grandchild should be less than any parent, and any right grandchild should be greater than any parent. Therefore, we must always consider the minimum and maximum values of the ancestors to ensure the current node falls within the correct range.

Time - O(n)

Space - O(n), Auxiliary space (generally it will be the height of the BST)

class Solution {

    private boolean isValid(TreeNode root, long min, long max){
        if(root == null) return true;
        if(root.val<=min || root.val>=max) return false;

        return isValid(root.left, min, root.val) 
                && isValid(root.right, root.val, max);
    }

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