LeetCode-in-All

98. Validate Binary Search Tree

Medium

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

A valid BST is defined as follows:

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:

Solution

using LeetCodeNet.Com_github_leetcode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsValidBST(TreeNode root) {
        return Solve(root, long.MinValue, long.MaxValue);
    }
    // we will send a valid range and check whether the root lies in the range
    // and update the range for the subtrees
    private bool Solve(TreeNode root, long left, long right) {
        if (root == null) {
            return true;
        }
        if (root.val <= left || root.val >= right) {
            return false;
        }
        return Solve(root.left, left, (long)root.val) && Solve(root.right, (long)root.val, right);
    }
}